Метрическая размерность (теория графов)

В теории графов метрическая размерность графа G — это минимальная мощность подмножества S при которой все остальные вершины однозначно определяются их расстояниями до вершин в S. вершин , Нахождение метрической размерности графа — NP-трудная задача; версия решения, определяющая, меньше ли размерность метрики заданного значения, является NP-полной .

Подробное определение

Для упорядоченного подмножества $W=\{w_{1},w_{2},\dots ,w_{k}\}$ вершин и вершины v в связном графе G представлением v относительно W является упорядоченный k -кортеж $r(v|W)=(d(v,w_{1}),d(v,w_{2}),\dots ,d(v,w_{k}))$ , где d ( x , y ) представляет расстояние между вершинами x и y . Множество W является разрешающим множеством (или позиционирующим множеством) для G , если каждые две вершины G имеют различные представления. Метрическая размерность G это минимальная мощность разрешающего множества для G. — Разрешающий набор, содержащий минимальное количество вершин, называется базисом (или эталонным набором) для G . Разрешающие множества для графов были независимо введены Слейтером (1975) и Харари и Мелтером (1976) , тогда как понятия разрешающего множества и метрической размерности были определены гораздо раньше в более общем контексте метрических пространств Блюменталем в его монографии «Теория». и приложения дистанционной геометрии . Графы являются особыми примерами метрических пространств с их внутренней метрикой пути.

Деревья

Если дерево является путем, его метрическая размерность равна единице. В противном случае пусть L обозначает множество листьев, вершин первой степени в дереве. Пусть K — множество вершин, степень которых больше двух и которые соединены путями вершин степени два с одним или несколькими листьями. Тогда метрическая размерность равна | Л | − | К |. Базис этой мощности можно сформировать, удалив из L один из листьев, связанных с каждой вершиной K. из ^[1] Тот же алгоритм действителен для линейного графа дерева, и, таким образом, любое дерево и его линейный граф имеют одинаковую метрическую размерность. ^[2]

Характеристики

В Чартране и др. (2000) доказано, что:

Метрическая размерность графа $G$ равна 1 тогда и только тогда, когда $G$ — путь.
Метрическая размерность $n-$ вершинного графа равна $n -1$ тогда и только тогда, когда он является полным графом .
Метрическая размерность $n$ -вершинного графа равна $n - 2$ тогда и только тогда, когда граф является полным двудольным графом $K s, t$ , расщепляемым графом. $K_{s}+{\overline {K_{t}}}(s\geq 1,t\geq 2)$ , или $K_{s}+(K_{1}\cup K_{t})(s,t\geq 1)$ .

Связь между порядком, метрическим размером и диаметром

Хуллер, Рагхавачари и Розенфельд (1996) доказывают неравенство $n\leq D^{\beta }+\beta$ для любого $n$ -вершинного графа с диаметром $D$ и метрический размер $\beta$ . Эти оценки следуют из того факта, что каждая вершина, не входящая в разрешающее множество, однозначно определяется вектором расстояния длины $\beta$ где каждая запись представляет собой целое число от 1 до $D$ (есть именно $D^{\beta }$ такие векторы). Однако граница достигается только для $D\leq 3$ или $\beta =1$ ; более точная граница $n\leq \left(\lfloor 2D/3\rfloor +1\right)^{\beta }+\beta \sum _{i=1}^{\lceil D/3\rceil }(2i-1)^{\beta -1}$ доказано Hernando et al. (2010) .

Для определенных классов графов могут соблюдаться меньшие границы. Например, Боду и др. (2018) доказали, что $n\leq (\beta D+4)(D+2)/8$ для деревьев (оценка точна для четных значений $D$ ) и оценка вида $n=O(D^{2}\beta )$ для внешнепланарных графов . Эти же авторы доказали, что $n\leq (D\beta +1)^{t-1}$ для графов без полного графа порядка $t$ в качестве минора , а также дал оценки для хордальных графов и графов ограниченной ширины дерева . Авторы Фуко и др. (2017a) доказали границы вида $n=O(D\beta ^{2})$ для графов интервалов и графов перестановок и границы вида $n=O(D\beta )$ для графов единичных интервалов , двудольных графов перестановок и кографов .

Вычислительная сложность

Сложность решения

Решение о том, является ли метрическая размерность графа не более чем заданным целым числом, является NP-полным. ^[3] ограниченной степени Он остается NP-полным для плоских графов , ^[4] расщепленные графы , двудольные графы и их дополнения , линейные графы двудольных графов, ^[5] графы единичного диска , ^[6] графы интервалов диаметра 2 и графы перестановок диаметра 2, ^[7] и графики ограниченной ширины дерева . ^[8]

Для любой фиксированной константы k графы метрической размерности не более k можно распознать за полиномиальное время путем проверки всех возможных k -кортежей вершин, но этот алгоритм не поддается обработке с фиксированными параметрами (для натурального параметра k размер решения ). Отвечая на вопрос, заданный Локштановым (2010) , Хартунг и Нихтерляйн (2013) показывают, что проблема решения метрической размерности является полной для параметризованного класса сложности W[2], подразумевая, что временная граница вида n ^{Хорошо )} то, что достигается с помощью этого наивного алгоритма, вероятно, является оптимальным, и что управляемый алгоритм с фиксированным параметром (для параметризации k ) вряд ли существует. Тем не менее, проблема становится разрешимой для фиксированных параметров, если ограничиться интервальными графиками . ^[7] и, в более общем плане, к графам ограниченной длины дерева, ^[9] такие как хордальные графы , графы перестановок или графы без тройных астероидов.

Решение о том, является ли метрическая размерность дерева не более заданным целым числом, может быть выполнено за линейное время. ^[10] существуют другие алгоритмы линейного времени Для кографов , ^[5] цепные графы , ^[11] и блочные графы кактусов ^[12] (класс, включающий как графы-кактусы , так и блочные графы ). Задача может быть решена за полиномиальное время на внешнепланарных графах . ^[4] Ее также можно решить за полиномиальное время для графиков ограниченного цикломатического числа : ^[5] но этот алгоритм снова не подходит для фиксированных параметров (для параметра «цикломатическое число»), поскольку показатель степени в полиноме зависит от цикломатического числа. Существуют управляемые алгоритмы с фиксированными параметрами для решения проблемы метрической размерности для параметров « вершинное покрытие », ^[13] "максимальное количество листьев", ^[14] и «модульная ширина». ^[9] Графы с ограниченным цикломатическим числом, числом покрытия вершин или максимальным числом листьев имеют ограниченную ширину дерева , однако остается открытой проблема определения сложности проблемы метрической размерности даже на графах с шириной дерева 2, то есть последовательно-параллельных графах . ^[9]

Сложность аппроксимации

Метрическая размерность произвольного n -вершинного графа может быть аппроксимирована за полиномиальное время с точностью до аппроксимации коэффициента $2\log n$ выражая это как проблему покрытия множества , проблему покрытия всего данного набора элементов как можно меньшим количеством наборов в данном семействе множеств . ^[15] В задаче покрытия множеств, сформированной на основе задачи метрической размерности, охватываемыми элементами являются ${\tbinom {n}{2}}$ пары вершин, которые необходимо различать, а наборы, которые могут их покрывать, — это наборы пар, которые можно отличить по одной выбранной вершине. Затем оценка аппроксимации получается путем применения стандартных алгоритмов аппроксимации для покрытия множеств. Альтернативный жадный алгоритм , который выбирает вершины в соответствии с разницей в энтропии между классами эквивалентности векторов расстояний до и после выбора, достигает еще лучшего коэффициента аппроксимации: $\log n+\log \log _{2}n+1$ . ^[16] Этот коэффициент аппроксимации близок к наилучшему из возможных, поскольку при стандартных предположениях теории сложности соотношение $(1-\epsilon )\log n$ не может быть достигнуто за полиномиальное время ни при каком $\epsilon >0$ . ^[16] Последняя сложность аппроксимации по-прежнему сохраняется для случаев, ограниченных субкубическими графами. ^[13] и даже к двудольным субкубическим графам. ^[17]

Ссылки

Примечания

^ Слейтер 1975 ; Харари и Мелтер 1976 ; Хуллер, Рагхавачари и Розенфельд, 1996 . Обратите внимание на нестандартное определение листьев дерева, данное Слейтером.
^ Фэн, Сюй и Ван 2013 .
^ Гари и Джонсон 1979 .
^ Jump up to: ^а ^б Díaz et al. 2012Диас и др. 2012
^ Jump up to: ^а ^б ^с Эпштейн, Левин и Вегингер, 2012 .
^ Хоффманн и Ванке 2013 .
^ Jump up to: ^а ^б Фуко и др. 2017б .
^ Ли и Пилипчук 2022 .
^ Jump up to: ^а ^б ^с Бельмонте и др. 2015 .
^ Слейтер 1975 ; Харари и Мелтер, 1976 .
^ Фернау и др. 2015 .
^ Хоффманн, Элтерман и Ванке, 2016 .
^ Jump up to: ^а ^б Хартунг и Нихтерляйн 2013 .
^ Эппштейн 2015 .
^ Хуллер, Рагхавачари и Розенфельд 1996 .
^ Jump up to: ^а ^б Гауптманн, Шмид и Виманн, 2012 г.
^ Хартунг 2014 .

Библиография

Боду, Лоран; Данкельманн, Питер; Фуко, Флоран; Хеннинг, Майкл А.; Мэри, Арно; Парро, Алин (2018), «Ограничение порядка графа с использованием его диаметра и метрической размерности: исследование с помощью разложения деревьев и размерности VC», SIAM Journal on Discrete Mathematics , 32 (2): 902–918, arXiv : 1610.01475 , дои : 10.1137/16M1097833 , S2CID 51882750
Бельмонте, Р.; Фомин Ф.В.; Головач, Пенсильвания; Рамануджан, М.С. (2015), «Метрическая размерность графов ограниченной ширины», на итальянском языке, GF; Пигиццини, Г.; Саннелла, Д.Т. (ред.), Математические основы информатики 2015 – MFCS 2015: 40-й международный симпозиум, Милан, Италия, 24–28 августа 2015 г., Труды , Конспекты лекций по информатике , том. 9235, Springer, стр. 115–126, номер документа : 10.1007/978-3-662-48054-0_10 , ISBN. 978-3-662-48053-3 .
Блюменталь, Л.М. (1953), Теория и приложения дистанционной геометрии , Кларендон, Оксфорд .
Бонне, Э.; Пурохит, Н. (2019), «Метрическое измерение, параметризованное шириной дерева», в Янсене, BMP; Телле, Дж. А. (ред.), Параметризованные и точные вычисления 2019 - IPEC 2019: 14-й международный симпозиум, Труды , Международные труды Лейбница по информатике (LIPIcs), том. 148, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, стр. 5:1–5:15, arXiv : 1907.08093 , doi : 10.4230/LIPIcs.IPEC.2019.5 .
Бучковский, П.; Шартран, Г .; Пуассон, К.; Чжан, П. (2003), «О $k$ -мерных графах и их базисах», Periodica Mathematica Hungarica , 46 (1): 9–15, doi : 10.1023/A:1025745406160 , MR 1975342 , S2CID 33390310 .
Шартран, Г .; Эрох, Л.; Джонсон, Массачусетс; Оллерманн, О.Р. (2000), «Разрешимость в графах и метрическая размерность графа», Discrete Applied Mathematics , 105 (1–3): 99–113, doi : 10.1016/S0166-218X(00)00198-0 , hdl : 10338.dmlcz/127843 , MR 1780464 .
Диас, Дж.; Поттонен, О.; Серна, MJ ; ван Леувен, Э.Дж. (2012), «О сложности метрического измерения» (PDF) , в Эпштейне, Лия; Феррагина, Паоло (ред.), Алгоритмы - ESA 2012: 20-й ежегодный европейский симпозиум, Любляна, Словения, 10–12 сентября 2012 г., Материалы , конспекты лекций по информатике, том. 7501, Springer, стр. 419–430, arXiv : 1107.2256 , doi : 10.1007/978-3-642-33090-2_37 , ISBN 978-3-642-33089-6 .
Эппштейн, Дэвид (2015), «Метрическая размерность, параметризованная максимальным числом листьев», Журнал графовых алгоритмов и приложений , 19 (1): 313–323, arXiv : 1506.01749 , doi : 10.7155/jgaa.00360 (неактивно с июля 2024 г.) 29), S2CID 1318601 {{citation}}:CS1 maint: DOI неактивен по состоянию на июль 2024 года ( ссылка ) .
Эпштейн, Лия; Левин, Асаф; Воегингер, Герхард Дж. (2012), «(Взвешенное) метрическое измерение графов: сложные и простые случаи», в Голумбике, Мартин Чарльз ; Стерн, Михал; Леви, Авивит; и др. (ред.), Теоретико-графовые концепции в информатике: 38-й международный семинар, WG 2012, Иерусалим, Израиль, 26–28 июня 2012 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 7551, стр. 114–125, номер документа : 10.1007/978-3-642-34611-8_14 , ISBN. 978-3-642-34610-1 .
Фэн, Мин; Сюй, Мин; Ван, Кайшунь (2013), «О метрической размерности линейных графиков», Discrete Applied Mathematics , 161 (6): 802–805, arXiv : 1107.4140 , doi : 10.1016/j.dam.2012.10.018 , S2CID 36010185 .
Фернау, Хеннинг; Heggernes, Пинар ; ван 'т Хоф, Пим; Мейстер, Дэниел; Саэй, Реза (2015), «Вычисление метрической размерности цепных графов», Information Processing Letters , 115 (9): 671–676, doi : 10.1016/j.ipl.2015.04.006 .
Фуко, Флоран; Мерциос, Джордж Б.; Насераср, Реза; Парро, Алин; Валиков, Петру (2017a), «Идентификация, доминирование местоположения и метрическая размерность на интервальных графах и графах перестановок. I. Границы», Theoretical Computer Science , 68 : 43–58, arXiv : 1507.08164 , doi : 10.1016/j.tcs.2017.01 .006 , S2CID 25244200
Фуко, Флоран; Мерциос, Джордж Б.; Насераср, Реза; Парро, Алин; Валиков, Петру (2017b), «Идентификация, доминирование местоположения и метрическая размерность на интервальных графах и графах перестановок. II. Алгоритмы и сложность», Algorithmica , 78 (3): 914–944, arXiv : 1405.2424 , doi : 10.1007/s00453- 016-0184-1 , S2CID 1520161 .
Гэри, MR ; Джонсон, Д.С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5 A1.5: GT61, с. 204.
Харари, Ф .; Мелтер, Р.А. (1976), «О метрической размерности графа», Ars Combinatoria , 2 : 191–195, MR 0457289 .
Хартунг, Зепп (2014), Исследование пространств параметров в условиях трудноразрешимых вычислений, докторская диссертация , Технический университет Берлина , получено 15 сентября 2015 г.
Хартунг, Зепп; Нихтерляйн, Андре (2013), «О параметризованной и аппроксимационной твердости метрической размерности», Конференция IEEE 2013 г. по вычислительной сложности (CCC), Стэнфорд, Калифорния, США, 5–7 июня 2013 г., Труды , IEEE, стр. 266– 276, arXiv : 1211.1636 , doi : 10.1109/CCC.2013.36 , ISBN 978-0-7695-4997-2 , S2CID 684505 .
Гауптманн, Матиас; Шмид, Ричард; Виманн, Клаус (2012), «Сложность аппроксимации проблемы метрической размерности», Журнал дискретных алгоритмов , 14 : 214–222, doi : 10.1016/j.jda.2011.12.010 , MR 2922072 .
Эрнандо, Кармен; Мора, Мерсе; Пелайо, Игнасио М.; Сира, Карлос; Вуд, Дэвид Р. (2010), «Экстремальная теория графов для метрической размерности и диаметра» , Electronic Journal of Combinatorics , 17 : #R30, doi : 10.37236/302 , hdl : 2117/8261 .
Хоффманн, Стефан; Эльтерман, Алина; Ванке, Эгон (2016), «Алгоритм с линейным временем для метрической размерности блочных графов кактусов», Theoretical Computer Science , 630 : 43–62, doi : 10.1016/j.tcs.2016.03.024
Хоффманн, Стефан; Ванке, Эгон (2013), «Метрическая размерность дисковых графов Габриэля является NP-полной», в Бар-Ной, Амоц; Халлдорссон, Магнус М. (ред.), Алгоритмы для сенсорных систем: 8-й Международный симпозиум по алгоритмам для сенсорных систем, беспроводных одноранговых сетей и автономных мобильных объектов, ALGOSENSORS 2012, Любляна, Словения, 13-14 сентября 2012 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, вып. 7718, Springer, стр. 90–92, arXiv : 1306.2187 , doi : 10.1007/978-3-642-36092-3_10 , ISBN 978-3-642-36091-6 , S2CID 9740623 .
Хуллер, С .; Рагхавачари, Б.; Розенфельд, А. (1996), «Ориентиры на графиках», Discrete Applied Mathematics , 70 (3): 217–229, doi : 10.1016/0166-218x(95)00106-2 , hdl : 10338.dmlcz/140702 .
Ли, Шаохуа; Пилипчук, Марцин (июль 2022 г.), «Твердость метрической размерности в графах постоянной ширины дерева», Algorithmica , 84 (11): 3110–3155, arXiv : 2102.09791 , doi : 10.1007/s00453-022-01005-y , S2CID 231979 414
Локштанов, Дэниел (2010), «Открытые проблемы - Параметризованная сложность и алгоритмы аппроксимации: метрическая размерность», в Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги; Маркс, Даниэль (ред.), Параметризованная сложность и алгоритмы аппроксимации , Материалы семинара Дагштуля, Дагштуль, Германия: Schloss Dagstuhl – Центр компьютерных наук Лейбница , номер документа : 10.4230/DagSemProc.09511.3 .
Слейтер, П.Дж. (1975), «Листья деревьев», Proc. 6-я Юго-восточная конференция по комбинаторике, теории графов и информатике (Флоридский Атлантический университет, Бока-Ратон, Флорида, 1975) , Congressus Numerantium, vol. 14, Виннипег: Utilitas Math., стр. 549–559, MR 0422062 .
Слейтер, П.Дж. (1988), «Доминирующие и эталонные множества в графе», Журнал математических и физических наук , 22 (4): 445–455, MR 0966610 .

[1] Слейтер 1975 ; Харари и Мелтер 1976 ; Хуллер, Рагхавачари и Розенфельд, 1996 . Обратите внимание на нестандартное определение листьев дерева, данное Слейтером.

[FOOTNOTEFengXuWang2013-2] Фэн, Сюй и Ван 2013 .

[FOOTNOTEGareyJohnson1979-3] Гари и Джонсон 1979 .

[FOOTNOTEDíazPottonenSernavan_Leeuwen2012-4] Jump up to: ^а ^б Díaz et al. 2012Диас и др. 2012

[FOOTNOTEEpsteinLevinWoeginger2012-5] Jump up to: ^а ^б ^с Эпштейн, Левин и Вегингер, 2012 .

[FOOTNOTEHoffmannWanke2013-6] Хоффманн и Ванке 2013 .

[FOOTNOTEFoucaudMertziosNaserasrParreau2017b-7] Jump up to: ^а ^б Фуко и др. 2017б .

[FOOTNOTELiPilipczuk2022-8] Ли и Пилипчук 2022 .

[FOOTNOTEBelmonteFominGolovachRamanujan2015-9] Jump up to: ^а ^б ^с Бельмонте и др. 2015 .

[10] Слейтер 1975 ; Харари и Мелтер, 1976 .

[FOOTNOTEFernauHeggernesvan_'t_HofMeister2015-11] Фернау и др. 2015 .

[FOOTNOTEHoffmannEltermanWanke2016-12] Хоффманн, Элтерман и Ванке, 2016 .

[FOOTNOTEHartungNichterlein2013-13] Jump up to: ^а ^б Хартунг и Нихтерляйн 2013 .

[FOOTNOTEEppstein2015-14] Эппштейн 2015 .

[FOOTNOTEKhullerRaghavachariRosenfeld1996-15] Хуллер, Рагхавачари и Розенфельд 1996 .

[FOOTNOTEHauptmannSchmiedViehmann2012-16] Jump up to: ^а ^б Гауптманн, Шмид и Виманн, 2012 г.

[FOOTNOTEHartung2014-17] Хартунг 2014 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]