Мінор обмеженої глибини

Неглибокий мінор або мінор обмеженої глибини — це обмежений вид мінора графа, в якому стягнуті підграфи мають малий діаметр. Неглибокі мінори ввели Плоткін, Рао та Сміт, але вони приписують визначення терміна Чарльзу Лейзерсону та Сівану Толедо^[3].

Визначення

Граф, що містить повний граф ${\displaystyle K_{4}}$ як 1-неглибокий мінор. Кожна з чотирьох підмножин усередині затінених прямокутників породжує підграф радіуса одиниця і існує ребро між будь-якими парами підмножин.

Один зі способів визначення мінора неорієнтованого графа ${\displaystyle G}$ полягає у вказанні підграфа ${\displaystyle H}$ графа ${\displaystyle G}$ і набору множин ${\displaystyle S_{i}}$ вершин графа ${\displaystyle G}$, що не перетинаються, кожна з яких утворює зв'язний породжений підграф ${\displaystyle H_{i}}$ графа ${\displaystyle H}$. Мінор має вершину ${\displaystyle v_{i}}$ для кожної підмножини ${\displaystyle S_{i}}$ і ребро ${\displaystyle v_{i}v_{j}}$_j, якщо існує ребро із ${\displaystyle S_{i}}$ до ${\displaystyle S_{j}}$, що належить ${\displaystyle H}$.

У цьому формулюванні ${\displaystyle d}$-неглибокий мінор (інша назва — мінор глибини ${\displaystyle d}$) — це мінор, який можна визначити вказаним вище чином з умовою, що кожен з підграфів ${\displaystyle H_{i}}$ має радіус, що не перевищує ${\displaystyle d}$, що означає, що підграф містить вершину ${\displaystyle c_{i}}$, відстань від якої до решти вершин підграфа ${\displaystyle H_{i}}$ не перевищує ${\displaystyle d}$. Зауважимо, що відстань тут вимірюється в числі дуг у графі ${\displaystyle H_{i}}$, а тому ця відстань може бути більшою за відстань у графі ${\displaystyle G}$^[3].

Часткові випадки

Мінори глибини нуль — це те саме, що підграфи даного графа. За досить великого ${\displaystyle d}$ (зокрема, не менші від числа вершин графа), мінори глибини ${\displaystyle d}$ збігаються з усіма мінорами графа^[3].

Класифікація сімейств графів

Нешріл та Оссона де Мендез використовували неглибокі мінори для поділу сімейств кінцевих графів на два типи. Вони кажуть, що сімейство графів ${\displaystyle F}$ подекуди щільне, якщо існує скінченне значення ${\displaystyle d}$, для якого множина мінорів глибини ${\displaystyle d}$ графів ${\displaystyle F}$ містить будь-який скінченний граф. В іншому випадку кажуть, що сімейство графів ніде не щільне^[5]. Цю термінологію виправдовує те, що якщо ${\displaystyle F}$ ніде не щільний клас графів, то (для будь-якого ${\displaystyle \varepsilon >0}$) графи з ${\displaystyle n}$ вершинами з ${\displaystyle F}$ мають ${\displaystyle O(n^{1+\varepsilon })}$ вершин. Таким чином, ніде не щільні графи є розрідженими графами.

Більш обмежений тип сімейств графів, описуваних подібним чином — сімейства графів з обмеженим розширенням. Це сімейства графів, для яких існує функція ${\displaystyle f}$, така, що відношення числа ребер до числа вершин у будь-якому мінорі глибини ${\displaystyle d}$ не перевищує ${\displaystyle f(d)}$^[7]. Якщо така функція існує і обмежена многочленом, то кажуть, що сімейство має поліноміальне розширення.

Теорема про відділення

Як показали Плоткін, Рао і Сміт, графи з виключеними неглибокими мінорами можна розбити аналогічно до розбиття в теоремі про сепаратор для планарних графів. Зокрема, якщо повний граф ${\displaystyle K_{h}}$ не є мінором глибини ${\displaystyle d}$ графа ${\displaystyle G}$ з ${\displaystyle n}$ вершинами, існує підмножина ${\displaystyle S}$ вершин графа ${\displaystyle G}$ розміру ${\displaystyle O(dh^{2}\log n+n/d)}$, така, що будь-яка зв'язна компонента графа ${\displaystyle G\backslash S}$ має максимум ${\displaystyle 2n/3}$ вершин. Результат є конструктивним — існують алгоритми з поліноміальним часом виконання, які знаходять такий сепаратор, або мінор ${\displaystyle K_{h}}$ глибини ${\displaystyle d}$. Як наслідок, Плоткін та інші показали, що з будь-якого сімейства графів, замкненого відносно мінорів, теорема про сепаратор виконується майже так само строго, як і для планарних графів.

Плоткін та інші також застосували ці результати для поділу сіток у методі скінченних елементів у великих розмірностях. Для цього неглибокі мінори необхідні, оскільки (за відсутності обмежень) сімейство сіток у розмірностях три і вище мають мінорами всі графи. Тенг поширив ці результати на ширший клас графів високої розмірності.

Дворак і Норін показали, що для класів, замкнутих відносно операції створення підграфів, із строгої сублінійності сепараторів випливає поліноміальність розширення.

Примітки

1. Мінор утворюється стягуванням ребер. Якщо деякий підграф стягується у вершину, говоритимемо про стягнутий підграф.
2. Plotkin, Rao, Smith, 1994.
3. Nešetřil, Ossona de Mendez, 2012, с. 62–65, розділ 4.2 "Shallow Minors".
4. Nešetřil, Ossona de Mendez, 2012.
5. Nešetřil, Ossona de Mendez, 2012, с. 100–102, розділ 5.3 "Classification of Classes by Clique Minors".
6. Nešetřil, Ossona de Mendez, 2012, с. 100, теорема 5.3.
7. Nešetřil, Ossona de Mendez, 2012, с. 104–107, розділ 5.5 "Classes with Bounded Expansion".
8. Алгоритм Плоткіна виконується за час ${\displaystyle O(mn/d)}$, де ${\displaystyle m}$ — число ребер. Вульф-Нильсен (Wulff-Nilsen, 2011) покращив цей час для нерозріджених графів до ${\displaystyle O(m+n^{2+\varepsilon }/d)}$.
9. Teng, 1998.
10. Dvořák, Norin, 2015, с. 3.

Література

• Zdeněk Dvořák, Sergey Norin. Strongly sublinear separators and polynomial expansion. — 2015. — arXiv:1504.04821.
• Serge Plotkin, Satish Rao, Warren D. Smith. Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA). — 1994. — С. 462–470..
• Shang-Hua Teng. Combinatorial aspects of geometric graphs // Comput. Geom.. — 1998. — Т. 9, вип. 4. — С. 277–287. — DOI:10.1016/S0925-7721(96)00008-9..
• Christian Wulff-Nilsen. Proc. 52nd IEEE Symp. Foundations of Computer Science (FOCS). — 2011. — С. 37–46. — DOI:10.1109/FOCS.2011.15.
• Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — (Algorithms and Combinatorics) — . — DOI:10.1007/978-3-642-27875-4.