Ограниченное расширение - Википедия - Bounded expansion

В теория графов, говорят, что семейство графов имеет ограниченное расширение если все это мелкие несовершеннолетние находятся разреженные графики. Многие естественные семейства разреженных графов имеют ограниченное расширение. Тесно связанное, но более сильное свойство, полиномиальное разложение, эквивалентно существованию теоремы о разделителях для этих семей. Семьи с этой недвижимостью имеют эффективные алгоритмы для проблем, включая проблема изоморфизма подграфов и проверка модели для теории графов первого порядка.

Определение и эквивалентные характеристики

А т-халый минор графа грамм определяется как граф, сформированный из грамм путем сжатия набора вершинно-непересекающихся подграфов радиуса т, и удалив оставшиеся вершины грамм. Семейство графов имеет ограниченное расширение, если существует функция ж так что в каждом т-положенный минор графа в семействе, отношение ребер к вершинам не превосходит ж(т).[1]

Эквивалентные определения классов ограниченных расширений таковы, что все мелкие миноры имеют хроматическое число ограниченный функцией т,[1] или что данное семейство имеет ограниченное значение топологический параметр. Таким параметром является инвариант графа который является монотонным при взятии подграфов, такой, что значение параметра может изменяться только контролируемым образом, когда граф разбит на части, и такое, что ограниченное значение параметра подразумевает, что граф имеет ограниченный вырождение.[2]

Полиномиальные разложения и теоремы о разделителях

Более сильное понятие полиномиальное разложение, что означает, что функция ж используется для ограничения плотности краев мелких миноров. многочлен. Если наследственное семейство графов подчиняется теорема о разделителе, заявив, что любой п-вершинный граф семейства можно разбить на части, не более чем п/ 2 вершины удалением О(пc) вершин для некоторой постоянной c <1, то это семейство обязательно имеет полиномиальное расширение. И наоборот, графы с полиномиальным расширением имеют теоремы о сублинейных разделителях.[3]

Классы графов с ограниченным расширением

Из-за связи между разделителями и расширением каждый семейство минорных замкнутых графов, включая семью планарные графы, имеет полиномиальное разложение. То же верно и для 1-планарные графы и, в более общем смысле, графы, которые могут быть вложены на поверхности ограниченного род с ограниченным числом пересечений на ребро, а также без бикликов строковые графики, поскольку все они подчиняются аналогичным теоремам о разделителях для плоских графов.[4][5][6][7] В высшем измерении Евклидовы пространства, графы пересечений систем шаров со свойством, что любая точка пространства покрывается ограниченным числом шаров, также подчиняются теоремам о разделении[8] что подразумевает полиномиальное разложение.

Хотя графы ограниченного толщина книги не имеют сублинейных разделителей,[9] они также имеют ограниченное расширение.[10] Другие графы ограниченного расширения включают графы ограниченной степени,[11] случайные графы ограниченной средней степени в Модель Эрдеша – Реньи,[12] и графы ограниченных номер очереди.[2][13]

Алгоритмические приложения

Экземпляры проблема изоморфизма подграфов в котором цель состоит в том, чтобы найти целевой граф ограниченного размера, как подграф большего графа, размер которого не ограничен, может быть решен в линейное время когда больший граф принадлежит семейству графов ограниченного расширения. То же верно и для поиск клик фиксированного размера, нахождение доминирующие наборы фиксированного размера или, в более общем смысле, свойств тестирования, которые могут быть выражены формулой ограниченного размера в первом порядке логика графиков.[14][15]

Для графов полиномиального разложения существуют схемы полиномиальной аппроксимации для установить проблему прикрытия, задача о максимальном независимом множестве, проблема доминирующего набора, и несколько других связанных проблем оптимизации графов.[16]

Рекомендации

  1. ^ а б Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «5.5 Классы с ограниченным расширением», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Springer, стр. 104–107, Дои:10.1007/978-3-642-27875-4, ISBN  978-3-642-27874-7, МИСТЕР  2920058.
  2. ^ а б Нешетржил, Ярослав; Оссона де Мендес, Патрис; Вуд, Дэвид Р. (2012), «Характеристики и примеры классов графов с ограниченным расширением», Европейский журнал комбинаторики, 33 (3): 350–373, arXiv:0902.3265, Дои:10.1016 / j.ejc.2011.09.008, МИСТЕР  2864421.
  3. ^ Дворжак, Зденек; Норин, Сергей (2015), Сильно сублинейные разделители и полиномиальное разложение, arXiv:1504.04821, Bibcode:2015arXiv150404821D
  4. ^ Нешетржил и Оссона де Мендес (2012), 14.2 Номер перехода, стр. 319–321.
  5. ^ Григорьев Александр; Бодландер, Ханс Л. (2007), «Алгоритмы для встраиваемых графов с несколькими пересечениями на ребро», Алгоритмика, 49 (1): 1–11, Дои:10.1007 / s00453-007-0010-х, МИСТЕР  2344391.
  6. ^ Дуймович, Вида; Эппштейн, Дэвид; Вуд, Дэвид Р. (2015), «Род, ширина дерева и местный номер скрещивания», Proc. 23-е Междунар. Symp. Графический рисунок (GD 2015), arXiv:1506.04380, Bibcode:2015arXiv150604380D.
  7. ^ Фокс, Джейкоб; Пах, Янош (2009), «Теорема о разделителе для строковых графов и ее приложения», Комбинаторика, теория вероятностей и вычисления, 19 (3): 371, Дои:10.1017 / s0963548309990459.
  8. ^ Миллер, Гэри Л.; Тэн, Шан-Хуа; Терстон, Уильям; Вавасис, Стивен А. (1997), "Разделители для сфер-упаковок и графов ближайших соседей", Журнал ACM, 44 (1): 1–29, Дои:10.1145/256292.256294, МИСТЕР  1438463.
  9. ^ Дуймович, Вида; Сидиропулос, Анастасиос; Вуд, Дэвид Р. (2015), 3-монотонные расширители, arXiv:1501.05020, Bibcode:2015arXiv150105020D
  10. ^ Нешетржил и Оссона де Мендес (2012), 14.5 Номер стека, стр. 327–328.
  11. ^ Нешетржил и Оссона де Мендес (2012), п. 307.
  12. ^ Нешетржил и Оссона де Мендес (2012), 14.1. Случайные графы (модель Эрдеша – Реньи), стр. 314–319.
  13. ^ Нешетржил и Оссона де Мендес (2012) С. 321–327.
  14. ^ Нешетржил и Оссона де Мендес (2012), 18.3 Проблема изоморфизма подграфов и булевы запросы, стр. 400–401.
  15. ^ Дворжак, Зденек; Кран, Даниэль; Томас, Робин (2010), «Определение свойств первого порядка для разреженных графов», Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010), IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 133–142, МИСТЕР  3024787.
  16. ^ Хар-Пелед, Сариэль; Куанруд, Кент (2015), «Алгоритмы аппроксимации для полиномиальных разложений и графов низкой плотности», Алгоритмы - ESA 2015: 23-й ежегодный европейский симпозиум, Патры, Греция, 14–16 сентября 2015 г., Материалы, Конспект лекций по информатике, 9294, Springer-Verlag, стр. 717–728, arXiv:1501.00721, Дои:10.1007/978-3-662-48350-3_60.