Минор ограниченной глубины (Bnukj kijguncyuukw ilrQnud)

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

Определение

Граф, имеющий полный граф K₄ в качестве 1-неглубокого минора. Каждое из четырёх подмножеств внутри затенённых прямоугольников порождает подграф радиуса единица и существует ребро между любыми парами подмножеств.

Один из способов определения минора неориентированного графа G заключается в указании подграфа H графа G и набора непересекающихся множеств S_i вершин графа G, каждое из которых образует связный порождённый подграф H_i графа H. Минор имеет вершину v_i для каждого подмножества S_i и ребро v_iv_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 нигде не плотный класс графов, то (для любого ε > 0) графы с n вершинами из F имеют O(n^1 + ε) вершин. Таким образом, нигде не плотные графы являются разреженными графами.

Более ограниченное семейство графов, описываемое подобным образом, это семейство графов с ограниченным расширением. Это семейства графов, для которых существует функция f, такая, что отношение числа рёбер к числу вершин в любом миноре глубины d не превосходит f(d). Если такая функция существует и ограничена многочленом, говорят, что семейство имеет полиномиальное расширение.

Теорема об отделении

Как показали Плоткин, Рао и Смит, графы с исключёнными неглубокими минорами могут быть разбиты аналогично разбиению в теореме о сепараторе для планарных графов. В частности, если полный граф K_h не является минором глубины d графа G с n вершинами, то существует подмножество S вершин графа G размера O(dh² log n + n/d), такое, что любая связная компонента графа G\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.