Ограниченное расширение
В теории графов , что семейство графов говорят имеет ограниченное расширение , если все его мелкие миноры являются разреженными графами . Многие естественные семейства разреженных графов имеют ограниченное расширение. Тесно связанное, но более сильное свойство, полиномиальное разложение , эквивалентно существованию теорем о разделителе для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для решения проблем, включая проблему изоморфизма подграфов и проверку моделей для теории графов первого порядка.
Определение и эквивалентные характеристики
[ редактировать ]t -мелкий минор графа G определяется как граф, сформированный из G путем сжатия набора непересекающихся по вершинам подграфов радиуса t и удаления оставшихся вершин G . Семейство графов имеет ограниченное расширение, если существует функция f такая, что в каждом t -мелком миноре графа в семействе отношение ребер к вершинам не превосходит f ( t ). [1]
Эквивалентные определения классов ограниченных расширений заключаются в том, что все мелкие миноры имеют хроматическое число, ограниченное функцией t , [1] или что данное семейство имеет ограниченное значение топологического параметра . Такой параметр представляет собой инвариант графа , монотонный относительно подграфов, такой, что значение параметра может изменяться только контролируемым образом при подразделении графа, и такой, что ограниченное значение параметра подразумевает, что граф имеет ограниченное вырождение . [2]
Теоремы о полиномиальном разложении и сепараторах
[ редактировать ]Более сильное понятие – полиномиальное разложение , означающее, что функция f, используемая для ограничения плотности ребер мелких миноров, является полиномом . Если семейство наследственных графов подчиняется теореме о разделителе , утверждающей, что любой n- вершинный граф в семействе можно разбить на части, содержащие не более n /2 вершин, удалением O ( n с ) вершин для некоторой константы c < 1, то это семейство обязательно имеет полиномиальное расширение. И наоборот, графы с полиномиальным разложением имеют теоремы о сублинейном разделителе. [3]
Классы графов с ограниченным расширением
[ редактировать ]Из-за связи между разделителями и расширением каждое минорно-замкнутое семейство графов , включая семейство планарных графов , имеет полиномиальное расширение. То же самое верно для 1-планарных графов и, в более общем плане, для графов, которые можно встроить в поверхности ограниченного рода с ограниченным числом пересечений на ребро, а также для без биклик струнных графов , поскольку все они подчиняются аналогичным теоремам о сепараторах. к планарным графам. [4] [5] [6] [7] В евклидовых пространствах более высокой размерности пересечений графы систем шаров со свойством, что любая точка пространства покрывается ограниченным числом шаров, также подчиняются теоремам о сепараторах. [8] что подразумевает полиномиальное разложение.
Хотя графы ограниченной толщины книги не имеют сублинейных разделителей, [9] они также имеют ограниченное расширение. [10] Другие графы ограниченного расширения включают графы ограниченной степени, [11] случайные графы ограниченной средней степени в модели Эрдеша–Реньи , [12] и графики числа ограниченной очереди . [2] [13]
Алгоритмические приложения
[ редактировать ]Экземпляры проблемы изоморфизма подграфов , цель которой состоит в том, чтобы найти целевой граф ограниченного размера как подграф большего графа, размер которого не ограничен, могут быть решены за линейное время, когда больший граф принадлежит семейству графов ограниченное расширение. То же самое верно для поиска клик фиксированного размера, поиска доминирующих наборов фиксированного размера или, в более общем плане, проверки свойств, которые могут быть выражены формулой ограниченного размера в логике графов первого порядка . [14] [15]
Для графов полиномиального расширения существуют схемы аппроксимации полиномиального времени для задачи покрытия множества , задачи максимального независимого множества , задачи доминирующего множества и нескольких других связанных задач оптимизации графа. [16]
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «5.5 Классы с ограниченным расширением», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Springer, стр. 104–107, номер документа : 10.1007/978-3-642-27875-4 , ISBN. 978-3-642-27874-7 , МР 2920058 .
- ↑ Перейти обратно: Перейти обратно: а б Нешетржил, Ярослав ; Оссона де Мендес, Патрис ; Вуд, Дэвид Р. (2012), «Характеристики и примеры классов графов с ограниченным расширением», Европейский журнал комбинаторики , 33 (3): 350–373, arXiv : 0902.3265 , doi : 10.1016/j.ejc.2011.09.008 , МР 2864421 , S2CID 2633083 .
- ^ Дворжак, Зденек; Норин, Сергей (2016), «Сильно сублинейные сепараторы и полиномиальное разложение», SIAM Journal on Discrete Mathematics , 30 (2): 1095–1101, arXiv : 1504.04821 , doi : 10.1137/15M1017569 , MR 3504982 , S2CID 27395 359
- ^ Нешетрил и Оссона де Мендес (2012) , 14.2 Номер пересечения, стр. 319–321.
- ^ Григорьев Александр; Бодлендер, Ханс Л. (2007), «Алгоритмы для встраиваемых графов с небольшим количеством пересечений на ребро» , Algorithmica , 49 (1): 1–11, doi : 10.1007/s00453-007-0010-x , MR 2344391 , S2CID 8174422 .
- ^ Дуймович, Вида ; Эппштейн, Дэвид ; Вуд, Дэвид Р. (2015), «Род, ширина дерева и число локальных скрещиваний», Proc. 23-й Международный. Симп. Рисование графика (GD 2015) , arXiv : 1506.04380 , Bibcode : 2015arXiv150604380D .
- ^ Фокс, Джейкоб ; Пах, Янош (2009), «Теорема о разделителе для строковых графов и ее приложения» (PDF) , Combinatorics, Probability and Computing , 19 (3): 371, doi : 10.1017/s0963548309990459 , S2CID 5705145 .
- ^ Миллер, Гэри Л .; Тэн, Шанхуа ; Терстон, Уильям ; Вавасис, Стивен А. (1997), «Сепараторы для сферических упаковок и графов ближайших соседей», Журнал ACM , 44 (1): 1–29, doi : 10.1145/256292.256294 , MR 1438463 .
- ^ Дуймович, Вида; Сидиропулос, Анастасиос; Вуд, Дэвид Р. (2015), 3-монотонные расширители , arXiv : 1501.05020 , Bibcode : 2015arXiv150105020D
- ^ Нешетрил и Оссона де Мендес (2012) , 14,5 Номер стека, стр. 327–328.
- ^ Нешетрил и Оссона де Мендес (2012) , стр. 307.
- ^ Нешетрил и Оссона де Мендес (2012) , 14.1 Случайные графики (модель Эрдеша – Реньи), стр. 314–319.
- ^ Нешетрил и Оссона де Мендес (2012) , стр. 321–327.
- ^ Нешетржил и Оссона де Мендес (2012) , 18.3 Проблема изоморфизма подграфов и логические запросы, стр. 400–401.
- ^ Дворжак, Зденек ; Краль, Даниэль ; Томас, Робин (2010), «Определение свойств первого порядка для разреженных графов», Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010) , IEEE Computer Soc., Лос-Аламитос, Калифорния, стр. 133–142, MR 3024787 .
- ^ Хар-Пелед, Сариэль ; Куанруд, Кент (2015), «Алгоритмы аппроксимации для графов полиномиального разложения и низкой плотности» , Алгоритмы - ESA 2015 , Конспекты лекций по информатике, том. 9294, Springer-Verlag, стр. 717–728, arXiv : 1501.00721 , doi : 10.1007/978-3-662-48350-3_60 , ISBN 978-3-662-48349-7 .