Ограниченное расширение графа

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

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

Минор глубины t графа G определяется как граф, образованный из G путём стягивания набора не имеющих общих вершин подграфов радиуса t и удаления оставшихся вершин. Семейство графов имеет ограниченное расширение, если существует функция 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] и графы с ограниченным числом очередей[2][12].

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

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

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

Примечания

1. Nešetřil, Ossona de Mendez, 2012, с. 104–107.
2. Nešetřil, Ossona de Mendez, Wood, 2012, с. 350–373.
3. Dvořák, Norin, 2015.
4. Nešetřil, Ossona de Mendez, 2012, с. 319–321, 14.2 Crossing Number.
5. Grigoriev, Bodlaender, 2007, с. 1–11.
6. Dujmović, Eppstein, Wood, 2015, с. 371.
7. Miller, Teng, Thurston, Vavasis, 1997, с. 1–29.
8. Dujmović, Sidiropoulos, Wood, 2015.
9. Nešetřil, Ossona de Mendez, 2012, с. 327–328; 14.5 Stack Number.
10. Nešetřil, Ossona de Mendez, 2012, с. 307.
11. Nešetřil, Ossona de Mendez, 2012, с. 314–319; 14.1 Random Graphs (Erdős–Rényi Model).
12. Nešetřil, Ossona de Mendez, 2012, с. 321–327.
13. Nešetřil, Ossona de Mendez, 2012, с. 400–401; 18.3 The Subgraph Isomorphism Problem and Boolean Queries.
14. Dvořák, Kráľ, Thomas, 2010, с. 133–142.
15. Har-Peled, Quanrud, 2015, с. 717–728.

Литература

• Jaroslav Nešetřil, Patrice Ossona de Mendez. 5.5 Classes with Bounded Expansion // Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — С. 104–107. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4.
• Jaroslav Nešetřil, Patrice Ossona de Mendez, David R. Wood. Characterisations and examples of graph classes with bounded expansion // European Journal of Combinatorics. — 2012. — Т. 33, вып. 3. — С. 350–373. — doi:10.1016/j.ejc.2011.09.008. — arXiv:0902.3265.
• Zdeněk Dvořák, Sergey Norin. Strongly sublinear separators and polynomial expansion. — 2015. — arXiv:1504.04821.
• Alexander Grigoriev, Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge // Algorithmica. — 2007. — Т. 49, вып. 1. — С. 1–11. — doi:10.1007/s00453-007-0010-x.
• Jacob Fox, János Pach. A separator theorem for string graphs and its applications // Combinatorics, Probability and Computing. — 2009. — Т. 19, вып. 3. — С. 371. — doi:10.1017/s0963548309990459.
• Gary L. Miller, Shang-Hua Teng, William Thurston, Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs // Journal of the ACM. — 1997. — Т. 44, вып. 1. — С. 1–29. — doi:10.1145/256292.256294.
• Vida Dujmović, David Eppstein, David R. Wood. Genus, treewidth, and local crossing number // Proc. 23rd Int. Symp. Graph Drawing (GD 2015). — 2015.
• Vida Dujmović, Anastasios Sidiropoulos, David R. Wood. 3-Monotone Expanders. — 2015. — arXiv:1501.05020.
• Zdeněk Dvořák, Daniel Kráľ, Robin Thomas. Deciding first-order properties for sparse graphs // Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). — IEEE Computer Soc., Los Alamitos, CA, 2010. — С. 133–142.
• Sariel Har-Peled, Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs // Algorithms – ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings. — Springer-Verlag, 2015. — Т. 9294. — С. 717–728. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-662-48350-3_60.