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

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

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

Література

• 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) — ISBN 978-3-642-27874-7. — DOI:10.1007/978-3-642-27875-4.