Обмежене розширення графа
Кажуть, що сімейство графів має обме́жене розши́рення, якщо всі його мінори обмеженої глибини є розрідженими графами. Багато природних сімейств розріджених графів мають обмежене розширення. Близька, але сильніша властивість, поліноміа́льне розши́рення, еквівалентне існуванню теорем розбиття для цих сімейств.
Сімейства з цими властивостями мають ефективні алгоритми для задач, у числі яких пошук ізоморфного підграфа і перевірка моделей для теорії першого порядку для графів.
Визначення та еквівалентні описи[ред. | ред. код]
Мінор глибини 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].
Алгоритмічні застосування[ред. | ред. код]
Примірник задачі ізоморфізму підграфа, в якій метою є пошук графа обмеженого розміру, що є підграфом більшого графа, розмір якого не обмежений, можна розв'язати за лінійний час, якщо більший граф належить до сімейства графів з обмеженим розширенням. Те ж саме стосується пошуку клік фіксованого розміру, пошуку домінівних множин фіксованого розміру, або, загальнішого випадку, перевірки властивостей, які можна виразити формулою обмеженого розміру в логіці графів[en] першого порядку[13][14].
Для графів із поліноміальним розширенням існують схеми наближення до поліноміального часу для задачі про покриття множини, задачі про максимальну незалежну множину, задачі про домінівну множину та деяких інших пов'язаних задач оптимізації[15].
Примітки[ред. | ред. код]
- ↑ а б Nešetřil, Ossona de Mendez, 2012, с. 104–107.
- ↑ а б Nešetřil, Ossona de Mendez, Wood, 2012, с. 350–373.
- ↑ Dvořák, Norin, 2015.
- ↑ Nešetřil, Ossona de Mendez, 2012, с. 319–321, 14.2 Crossing Number.
- ↑ Grigoriev, Bodlaender, 2007, с. 1–11.
- ↑ Dujmović, Eppstein, Wood, 2015, с. 371.
- ↑ Miller, Teng, Thurston, Vavasis, 1997, с. 1–29.
- ↑ Dujmović, Sidiropoulos, Wood, 2015.
- ↑ Nešetřil, Ossona de Mendez, 2012, с. 327–328; 14.5 Stack Number.
- ↑ Nešetřil, Ossona de Mendez, 2012, с. 307.
- ↑ Nešetřil, Ossona de Mendez, 2012, с. 314–319; 14.1 Random Graphs (Erdős–Rényi Model).
- ↑ Nešetřil, Ossona de Mendez, 2012, с. 321–327.
- ↑ Nešetřil, Ossona de Mendez, 2012, с. 400–401; 18.3 The Subgraph Isomorphism Problem and Boolean Queries.
- ↑ Dvořák, Kráľ, Thomas, 2010, с. 133–142.
- ↑ 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:
- 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. — arXiv:0902.3265. — DOI:.
- 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:.
- Jacob Fox, János Pach. A separator theorem for string graphs and its applications // Combinatorics, Probability and Computing. — 2009. — Т. 19, вип. 3. — С. 371. — DOI:.
- 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:.
- 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: