В теории графов , то метрическая размерность графа G является минимальной мощностью подмножества S вершин таким образом, что все остальные вершины однозначно определяются их расстояниями с вершинами в S . Нахождение метрической размерности графа - NP-трудная задача; версия решения, определяющая, меньше ли размер метрики заданного значения, является NP-полной .
Подробное определение
Для упорядоченного подмножества вершин и вершины v связного графа G представлением v относительно W является упорядоченный k -набор, где d ( x , y ) представляет собой расстояние между вершинами x и y . Множество W является разрешающим множеством (или определяющим множеством) для G, если каждые две вершины G имеют разные представления. Метрическая размерность G минимальное количество элементов разделяющего набора для G . Разрешающее множество , содержащее минимальное число вершин называются базисом (или опорным набором) для G . Разрешающие множества для графов были независимо введены Слэтером (1975) и Харари и Мелтером (1976) , в то время как концепции разрешающего множества и метрической размерности были определены намного раньше в более общем контексте метрических пространств Блюменталем в его монографии Теория и приложения дистанционной геометрии . Графы являются частными примерами метрических пространств с их внутренней метрикой путей.
Деревья
Slater (1975) (см. Также Harary & Melter (1976) и Khuller, Raghavachari & Rosenfeld (1996) ) дает следующую простую характеристику метрической размерности дерева . Если дерево представляет собой путь, его метрическое измерение равно единице. В противном случае пусть L обозначает набор вершин первой степени в дереве (обычно называемых листьями, хотя Слейтер использует это слово по-другому). Пусть K будет множеством вершин, степень которых больше двух, и которые соединены путями с вершинами степени два с одним или несколькими листами. Тогда метрическая размерность | L | - | K |, Основа этой мощности может быть сформирована путем удаления из L одного из листьев , связанный с каждой вершиной из K . Тот же алгоритм действителен для линейного графа дерева, что доказано Feng, Xu & Wang (2013) (и, таким образом, любое дерево и его линейный граф имеют одинаковую метрическую размерность).
Характеристики
В Chartrand et al. (2000) доказано, что:
- Метрическая размерность графа G равна 1 тогда и только тогда, когда G - путь.
- Метрическая размерность графа с n вершинами равна n - 1 тогда и только тогда, когда это полный граф .
- Метрическая размерность графа с n вершинами равна n - 2 тогда и только тогда, когда граф является полным двудольным графом K s , t , расщепленным графом , или же .
Связь между порядком, метрическим размером и диаметром
Khuller, Raghavachari & Rosenfeld (1996) доказывают неравенстводля любого n -вершинного графа диаметра D и метрической размерности β. Эта граница следует из того факта, что каждая вершина, не входящая в разрешающее множество, однозначно определяется вектором расстояний длины β, где каждая запись является целым числом от 1 до D (есть ровнотакие векторы). Однако оценка достигается только для или же ; более точная границадоказано Hernando et al. (2010) .
Для определенных классов графов могут выполняться меньшие границы. Например, Beaudou et al. (2018) доказали, чтодля деревьев (граница жесткая для четных значений D ) и граница видадля внешнепланарных графов . Те же авторы доказали, чтодля графов без полного графа порядка t как минор, а также дал оценки для хордовых графов и графов с ограниченной древесной шириной . Авторы Foucaud et al. (2017a) доказали оценки видадля интервальных графов и графов перестановок и границ видадля графов единичных интервалов , двудольных графов перестановок и кографов .
Вычислительная сложность
Сложность решения
Решение о том, является ли метрическая размерность графа не более чем заданным целым числом, является NP-полным ( Garey & Johnson 1979 ). Он остается NP-полным для плоских графов ограниченной степени ( Díaz et al.2012 ), расщепленных графов , двудольных графов и их дополнений , линейных графов двудольных графов ( Epstein, Levin & Woeginger 2012 ), графов единичных дисков ( Hoffmann & Wanke 2012). ), интервальные графы диаметра 2 и графы перестановок диаметра 2 ( Foucaud et al. 2017b ).
Для любой фиксированной константы k графики с метрической размерностью не более k могут быть распознаны за полиномиальное время путем тестирования всех возможных k -наборов вершин, но этот алгоритм не является управляемым с фиксированным параметром (для естественного параметра k размер решения ). Отвечая на вопрос, поставленный Локштановым (2010) , Хартунг и Нихтерлейн (2013) показывают, что проблема решения метрической размерности является полной для параметризованного класса сложности W [2], подразумевая, что временная граница формы n O ( k ), как достигнута с помощью этого наивного алгоритма, вероятно, является оптимальным, и что алгоритм с фиксированными параметрами (для параметризации с помощью k ) вряд ли существует. Тем не менее, проблема становится решаемой с фиксированными параметрами, когда она ограничивается интервальными графами ( Foucaud et al., 2017b ) и, в более общем смысле, графами с ограниченной древовидной длиной ( Belmonte et al. 2015 ), такими как хордовые графы , графы перестановок или астероидные графы. трижды свободные графы.
Решить, является ли метрическая размерность дерева не более чем заданным целым числом, можно сделать за линейное время ( Slater 1975 ; Harary & Melter 1976 ). Существуют и другие алгоритмы линейного времени для кографов ( Epstein, Levin & Woeginger 2012 ), цепных графов ( Fernau et al. 2015 ) и блочных графов кактусов ( Hoffmann, Elterman & Wanke 2016 ) (класс, включающий как графы кактусов, так и блочные графы ). Проблема может быть решена за полиномиальное время на внешнепланарных графах ( Диас и др., 2012 ). Он также может быть решен за полиномиальное время для графов с ограниченным цикломатическим числом ( Epstein, Levin & Woeginger 2012 ), но этот алгоритм снова не является управляемым с фиксированным параметром (для параметра «цикломатическое число»), потому что показатель степени в полиноме зависит от цикломатическое число. Существуют управляемые алгоритмы с фиксированными параметрами для решения проблемы метрической размерности для параметров « вершинное покрытие » ( Hartung & Nichterlein, 2013 ), «максимальное количество листьев» ( Eppstein, 2015 ) и «модульная ширина» ( Belmonte et al., 2015 ). Графы с ограниченным цикломатическим числом, числом вершинных покрытий или максимальным числом листьев имеют ограниченную ширину дерева , однако определение сложности проблемы метрической размерности даже на графах с шириной дерева 2, то есть последовательно-параллельных графах, является открытой проблемой ( Belmonte et al. др. 2015 ). С отрицательной стороны для общих значений ширины дерева было доказано, что проблема является W [1]-сложной при параметризации шириной пути (и, следовательно, также шириной дерева) входного графа ( Bonnet & Purohit 2019 ).
Сложность аппроксимации
Метрическая размерность произвольного п -vertex графа может быть аппроксимирована в полиномиальное время с точностью до коэффициента аппроксимации ввыражая ее как проблему покрытия множества , проблему покрытия всего данного набора элементов как можно меньшим количеством множеств в данном семействе множеств ( Khuller, Raghavachari & Rosenfeld 1996 ). В задаче о множественном покрытии, сформированной из задачи о метрическом измерении, элементы, которые должны быть охвачены, - этопары вершин, которые необходимо выделить, и множества, которые могут покрывать их, - это множества пар, которые можно различить по одной выбранной вершине. Оценка аппроксимации затем следует путем применения стандартных алгоритмов аппроксимации для покрытия множества. Альтернативный жадный алгоритм, который выбирает вершины в соответствии с разницей в энтропии между классами эквивалентности векторов расстояний до и после выбора, обеспечивает еще лучший коэффициент аппроксимации,( Hauptmann, Schmied & Viehmann 2012 ). Этот коэффициент аппроксимации близок к наилучшему возможному, так как при стандартных предположениях теории сложности соотношение не может быть достигнута за полиномиальное время ни для каких ( Hauptmann, Schmied & Viehmann 2012 ). Последняя трудность аппроксимации все еще сохраняется для случаев, ограниченных субкубическими графами ( Hartung & Nichterlein, 2013 ), и даже двудольными субкубическими графами, как показано в докторской диссертации Хартунга ( Hartung 2014 ).
Рекомендации
- Боду, Лоран; Данкельманн, Питер; Фуко, Флоран; Хеннинг, Майкл А .; Мэри, Арно; Парро, Алин (2018), «Ограничение порядка графа с использованием его диаметра и метрического измерения: исследование посредством древовидной декомпозиции и измерения VC», SIAM Journal on Discrete Mathematics , 32 (2): 902–918, arXiv : 1610.01475 , DOI : 10,1137 / 16M1097833 , S2CID 51882750
- Belmonte, R .; Фомин Ф.В. Головач П.А.; Рамануджан, М.С. (2015), «Метрическая размерность графов с ограниченной шириной», на итальянском языке, GF; Pighizzini, G .; Саннелла, Д.Т. (ред.), Математические основы компьютерных наук 2015 - MFCS 2015: 40-й Международный симпозиум, Милан, Италия, 24-28 августа 2015 г., Труды , Лекционные заметки по компьютерным наукам , 9235 , Springer, стр. 115–126 , DOI : 10.1007 / 978-3-662-48054-0_10.
- Блюменталь, Л. М. (1953), Теория и приложения дистанционной геометрии , Кларендон, Оксфорд..
- Bonnet, E .; Пурохит, Н. (2019), «Метрические размеры, параметризованные Treewidth», в Jansen, 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.
- Buczkowski, P .; Chartrand, G .; Пуассон, С .; Zhang, P. (2003), "О К - мерных графов и их основания", Periodica Mathematica Hungarica , 46 (1): 9-15, DOI : 10,1023 / A: 1025745406160 , MR 1975342 , S2CID 33390310.
- Chartrand, G .; Eroh, L .; Джонсон, Массачусетс; Оллерманн, О. Р. (2000), «Разрешимость в графах и метрическая размерность графа», Дискретная прикладная математика , 105 (1–3): 99–113, DOI : 10.1016 / S0166-218X (00) 00198-0 , hdl : 10338.dmlcz / 127843 , Руководство по ремонту 1780464.
- Díaz, J .; Pottonen, O .; Серна, MJ; ван Леувен, EJ (2012), "О сложности метрической размерности" (PDF) , в Эпштейне, Лия; Феррагина, Паоло (ред.), Алгоритмы - ESA 2012: 20-й ежегодный европейский симпозиум, Любляна, Словения, 10-12 сентября 2012 г., Proceedings , Lecture Notes in Computer Science, 7501 , Springer, pp. 419–430, arXiv : 1107.2256 , DOI : 10.1007 / 978-3-642-33090-2_37.
- Эппштейн, Дэвид (2015), «Измерение метрики, параметризованное максимальным числом листьев», Журнал алгоритмов и приложений графов , 19 (1): 313–323, arXiv : 1506.01749 , doi : 10.7155 / jgaa.00360 , S2CID 1318601.
- Эпштейн, Лия; Левин, Асаф; Woeginger, Gerhard J. (2012), «(Взвешенная) метрическая размерность графов: сложные и простые случаи», в Golumbic, Martin Charles ; Стерн, Михал; Леви, Авивит; и другие. (ред.), Теоретико-графические концепции в компьютерных науках: 38-й международный семинар, WG 2012, Иерусалим, Израиль, 26-28 июня 2012 г., Revised Selected Papers , Lecture Notes in Computer Science, 7551 , pp. 114–125, doi : 10.1007 / 978-3-642-34611-8_14.
- Фэн, Мин; Сюй, Мин; Ван, Кайшун (2013), «О метрической размерности линейных графов», Дискретная прикладная математика , 161 (6): 802–805, arXiv : 1107.4140 , doi : 10.1016 / j.dam.2012.10.018 , S2CID 36010185.
- Фернау, Хеннинг; Хеггернес, Пинар ; ван 'т Хоф, Пим; Мейстер, Дэниел; SAEI, Реза (2015), "Вычисление метрической размерности для цепных графов", Information Processing Letters , 115 (9): 671-676, DOI : 10.1016 / j.ipl.2015.04.006.
- Фуко, Флоран; Мерциос, Джордж Б .; Насераср, Реза; Парро, Алин; Валиков, Петру (2017a), «Идентификация, доминирование местоположения и метрическая размерность на интервальных и перестановочных графах. I. Границы», Теоретическая информатика , 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.
- Garey, MR ; Джонсон, Д.С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 0-7167-1045-5A1.5: GT61, стр. 204.
- Harary, F .; Мелтер, Р.А. (1976), «О метрической размерности графа», Ars Combinatoria , 2 : 191–195, MR 0457289.
- Хартунг, Зепп (2014), Исследование пространств параметров при решении вычислительной сложности, докторская диссертация , Технический университет Берлина , получено 15 сентября 2015 г..
- Хартунг, Зепп; Нихтерлейн, Андре (2013), «О параметризованной и аппроксимационной сложности метрической размерности», Конференция IEEE по вычислительной сложности (CCC) 2013 г., Стэнфорд, Калифорния, США, 5-7 июня 2013 г., Proceedings , IEEE, стр. 266– 276, Arxiv : 1211,1636 , DOI : 10,1109 / CCC.2013.36 , S2CID 684505.
- Гауптманн, Матиас; Шмид, Ричард; Viehmann, Клаус (2012), "Аппроксимация сложность задачи метрической размерности", журнал дискретных алгоритмов , 14 : 214-222, DOI : 10.1016 / j.jda.2011.12.010 , МР 2922072.
- Эрнандо, Кармен; Мора, Мерсе; Pelayo, Ignacio M .; Сеара, Карлос; Вуд, Дэвид Р. (2010), «Экстремальная теория графов для метрической размерности и диаметра» , Электронный журнал комбинаторики , 17 : # R30, DOI : 10,37236 / 302.
- Хоффманн, Стефан; Эльтерман, Алина; Ванке, Эгон (2016), «Алгоритм линейного времени для метрической размерности блочных графов кактусов», Теоретическая информатика , 630 : 43–62, DOI : 10.1016 / j.tcs.2016.03.024
- Хоффманн, Стефан; Ванке, Эгон (2012), «Метрическая размерность графов блочных дисков Габриэля является NP-полной», в Бар-Ной, Амоц; Халлдорссон, Магнус М. (ред.), Алгоритмы для сенсорных систем: 8-й Международный симпозиум по алгоритмам для сенсорных систем, беспроводных специальных сетей и автономных мобильных объектов, ALGOSENSORS 2012, Любляна, Словения, 13-14 сентября 2012 г., Отредактированные избранные статьи , Lecture Notes в области компьютерных наук, 7718 , Springer, С. 90-92,. Arxiv : 1306.2187 , DOI : 10.1007 / 978-3-642-36092-3_10 , S2CID 9740623.
- Хуллер, С .; Raghavachari, B .; Розенфельд, А. (1996), "Ориентиры в графах", Дискретная прикладная математика , 70 (3): 217-229, DOI : 10.1016 / 0166-218x (95) 00106-2 , ЛВП : 10338.dmlcz / 140702.
- Локштанов, Даниэль (2010), «Открытые задачи - параметризованная сложность и аппроксимационные алгоритмы: метрическая размерность», Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги; Маркс, Даниэль (ред.), Параметризованная сложность и алгоритмы приближения , Dagstuhl Seminar Proceedings, Dagstuhl, Германия: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
- Slater, PJ (1975), "Листья деревьев", Proc. 6-я Юго-Восточная конференция по комбинаторике, теории графов и вычислениям (Флоридский Атлантический университет, Бока-Ратон, Флорида, 1975) , Congressus Numerantium, 14 , Winnipeg: Utilitas Math., Стр. 549–559, MR 0422062.
- Слейтер, П.Дж. (1988), «Доминирующие и ссылочные множества в графе», Журнал математических и физических наук , 22 (4): 445–455, MR 0966610.