В теории графов говорят, что семейство графов имеет ограниченное расширение, если все его мелкие миноры являются разреженными графами . Многие естественные семейства разреженных графов имеют ограниченное расширение. Тесно связанное, но более сильное свойство, полиномиальное разложение , эквивалентно существованию теорем о разделении для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы решения проблем, включая проблему изоморфизма подграфов и проверку моделей для теории графов первого порядка.
Определение и эквивалентные характеристики
A T -shallow минор графа G называется граф формируется из G стягивания набора вершин-непересекающихся подграфов радиуса т , и удаления оставшихся вершин G . Семейство графов имеет ограниченное расширение, если существует функция f такая, что в каждом t- мелком миноре графа в семействе отношение ребер к вершинам не превосходит f ( t ). [1]
Эквивалентные определения классов ограниченных расширений заключаются в том, что все мелкие миноры имеют хроматическое число, ограниченное функцией t , [1] или что данное семейство имеет ограниченное значение топологического параметра . Такой параметр представляет собой инвариант графа, который является монотонным относительно взятия подграфов, такой, что значение параметра может изменяться только контролируемым образом, когда граф разбит на части, и такой, что ограниченное значение параметра подразумевает, что граф имеет ограниченную вырожденность . [2]
Полиномиальные разложения и теоремы о разделителях
Более сильным понятием является полиномиальное разложение , означающее, что функция f, используемая для ограничения плотности краев мелких миноров, является полиномом . Если наследственное семейство графов подчиняется теореме о разделителе , гласящей, что любой граф с n- вершинами в семействе можно разбить на части с не более чем n / 2 вершинами путем удаления O ( n c ) вершин для некоторой константы c <1, то это семейство обязательно имеет полиномиальное расширение. И наоборот, графы с полиномиальным расширением имеют теоремы о сублинейных разделителях. [3]
Классы графов с ограниченным расширением
Из-за связи между разделителями и расширением каждое семейство минорно-замкнутых графов , включая семейство плоских графов , имеет полиномиальное расширение. То же самое верно для 1-планарных графов и, в более общем смысле, для графов, которые могут быть вложены на поверхности ограниченного рода с ограниченным числом пересечений на ребро, а также для строковых графов без бикликов , поскольку все они подчиняются аналогичным теоремам о разделителях к планарным графам. [4] [5] [6] [7] В более мерных евклидовых пространства , пересечения графики систем шаров с тем свойством , что любая точка пространства , охватываемая ограниченным числом шаров также ПОДЧИНИТЬСЯ теоремы сепаратора [8] , что означает , многочлен расширение.
Хотя графы ограниченной книжной толщины не имеют сублинейных разделителей, [9] они также имеют ограниченное расширение. [10] Другие графики ограниченного расширения включают в себя графики ограниченной степени, [11] случайные графы ограниченной средней степени в модели Эрдеш-Рении , [12] и графиков ограниченного числа очередей . [2] [13]
Алгоритмические приложения
Примеры проблемы изоморфизма подграфов, в которых цель состоит в том, чтобы найти целевой граф ограниченного размера, как подграф большего графа, размер которого не ограничен, могут быть решены за линейное время, когда больший граф принадлежит семейству графов ограниченное расширение. То же самое верно для поиска клик фиксированного размера, поиска доминирующих множеств фиксированного размера или, в более общем смысле, тестирования свойств, которые могут быть выражены формулой ограниченного размера в логике графов первого порядка . [14] [15]
Для графиков полиномиального разложения, существует схемы аппроксимации полинома времени для задачи набора крышки , максимальные независимые множество проблемы , доминирующее множество проблем , и ряд других связанных с этим проблемы график оптимизации. [16]
Рекомендации
- ^ a b Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «5.5 Классы с ограниченным расширением», разреженность: графики, структуры и алгоритмы , алгоритмы и комбинаторика, 28 , Springer, стр. 104–107, DOI : 10.1007 / 978-3-642- 27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
- ^ а б Нешетржил, Ярослав ; Оссона де Мендес, Патрис ; Вуд, Дэвид Р. (2012), «Характеристики и примеры классов графов с ограниченным расширением», Европейский журнал комбинаторики , 33 (3): 350–373, arXiv : 0902.3265 , doi : 10.1016 / j.ejc.2011.09.008 , Руководство по ремонту 2864421.
- ^ Дворжак, Зденек; Норин, Сергей (2016), «Сильно сублинейные разделители и полиномиальное разложение», журнал SIAM по дискретной математике , 30 (2): 1095–1101, arXiv : 1504.04821 , doi : 10.1137 / 15M1017569 , MR 3504982
- ^ Nešetřil & Ossona де Мендес (2012) , 14,2 Crossing Число, стр. 319-321.
- ^ Григорьев Александр; Бодлендер, Ханс Л. (2007), «Алгоритмы для графов, встраиваемых с несколькими пересечениями на ребро» , Algorithmica , 49 (1): 1–11, DOI : 10.1007 / s00453-007-0010-x , MR 2344391.
- ^ Дуймович, Вида; Эпштейн, Дэвид ; Вуд, Дэвид Р. (2015), «Род, ширина дерева и местный номер пересечения», Proc. 23-е Междунар. Symp. График (GD 2015) , arXiv : 1506.04380 , Bibcode : 2015arXiv150604380D.
- ^ Фокс, Джейкоб ; Пах, Янош (2009), "Теорема о разделителе для строковых графов и ее приложения", Комбинаторика, вероятность и вычисления , 19 (3): 371, doi : 10.1017 / s0963548309990459.
- ^ Миллер, Гэри Л .; Тэн, Шан-Хуа ; Терстон, Уильям ; Vavasis, Стивен А. (1997), "Сепараторы для сферы-насадок и ближайших соседних графов", Журнал ACM , 44 (1): 1-29, DOI : 10,1145 / 256292,256294 , MR 1438463.
- ^ Дуймович, Вида; Сидиропулос, Анастасиос; Вуд, Дэвид Р. (2015), 3-Monotone Expanders , arXiv : 1501.05020 , Bibcode : 2015arXiv150105020D
- ^ Nešetřil & Ossona де Мендес (2012) , 14,5 Stack Количество, стр. 327-328.
- ^ Nešetřil & Ossona де Мендес (2012) , стр. 307.
- ^ Nešetřil & Ossona де Мендес (2012) , 14,1 случайных графов (Erdős-Реньи модели), стр. 314-319.
- ^ Nešetřil & Ossona де Мендес (2012) , стр. 321-327.
- ^ Nešetřil & Ossona де Мендес (2012) , 18,3 подграф Изоморфизм Проблема и Boolean Запросы, стр. 400-401.
- ^ Дворжак, Зденек ; Krá, Daniel ; Томас, Робин (2010), "Определение свойств первого порядка для разреженных графов", Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 133–142, MR 3024787.
- ^ Хар-Пелед, Сариэль ; Куанруд, Кент (2015), «Алгоритмы приближения для полиномиальных расширений и графов с низкой плотностью» , Алгоритмы - ESA 2015: 23-й ежегодный европейский симпозиум, Патры, Греция, 14–16 сентября 2015 г., Труды , Лекционные заметки по информатике 9294 , Springer-Verlag, стр. 717–728, arXiv : 1501.00721 , doi : 10.1007 / 978-3-662-48350-3_60.