Двумерность

Постановка задачи

Теория двумерности включает обобщенные техники разработки эффективных алгоритмов с фиксированными параметрами и алгоритмов аппроксимации для широкого круга NP-полных графовых задач на широком круге графов. Эта теория применяется к графовым задачам, которые являются «двумерными» в следующем смысле: (1) значение решения для графа, представленного в виде решетки [math]\displaystyle{ k \times k \; }[/math], и подобных ему графов растет вместе с k, обычно как [math]\displaystyle{ \Omega (k^2) \; }[/math]; (2) значение решения уменьшается при сжатии ребер графа и, возможно, при удалении ребер. Многие задачи являются двумерными; можно привести такие классические примеры, как вершинное покрытие, доминирующее множество и разрывающее множество вершин.

Классы графов

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

Первые два класса задач относятся к вложениям в плоскость. Граф является планарным, если он может быть изображен на плоскости или сфере без пересечения дуг. Граф имеет (эйлеров) род не более g, если он может быть изображен на плоскости с эйлеровой характеристикой g. Класс графов имеет ограниченный род, если каждый граф класса имеет род не более g при фиксированном g.

Следующие три класса задач касаются исключения миноров. Пусть дано ребро e = {v, w} в графе G. Сжатие ребра e в графе G заключается в определении вершин v и w в G и удалении всех циклов и дублирующихся ребер. Граф H, полученный в результате последовательности таких операций сжатия ребер в исходном графе G, называется сжатием графа G. Граф H называется минором графа G, если H является подграфом некоторого сжатия G. Класс графов C является замкнутым относительно операции взятия минора, если любой минор любого графа из C также является членом C. Класс графов C, замкнутый относительно операции взятия минора, является свободным от H-миноров, если [math]\displaystyle{ H \notin C \; }[/math]. В более общем смысле, термин «свободный от H-миноров» относится к любому классу графов, замкнутому относительно операции взятия минора, который не включает некоторый фиксированный граф H. Граф с однократным пересечением представляет собой минор графа, который может быть изображен на плоскости так, что в нем будет пересекаться не более одной пары ребер. Класс графов, замкнутый относительно операции взятия минора, является свободным от миноров с однократным пересечением, если из него исключен фиксированный граф с однократным пересечением. Апексным графом называется граф, который становится планарным при удалении из него некоторой вершины. Класс графов является свободным от апексных миноров, если из него исключен некоторый фиксированный апексный граф.

Двумерные параметры

Неявно понятие «двумерный» подразумевалось в различных работах [2, 5, 10, 11], однако первое явное упоминание было сделано в работе [3].

Во-первых, подход с использованием параметров – это альтернативный взгляд на задачи оптимизации. Параметр P представляет собой функцию, отображающую графы на неотрицательные целые числа. Задача разрешимости, связанная с P, для заданного графа G и неотрицательного целого числа k спрашивает, выполняется ли соотношение [math]\displaystyle{ P(G) \le k \; }[/math]. Многие задачи оптимизации могут быть сформулированы в виде подобных задач разрешимости для графового параметра P.

Параметр является g(r)-двумерным (или просто двумерным), если он равен не менее чем g(r) в «графе-решетке» размером [math]\displaystyle{ r \times r \; }[/math] и если он не повышается при взятии миноров (g(r)-минорно-двумерный) либо выполнении сжатий (g(r)-сжато-двумерный). Точное определение «графа-решетки» зависит от класса допустимых графов и от того, рассматривается ли минорная двумерность или двумерность со сжатием. Для случая минорной двумерности и для любого класса графов, свободного от H-миноров, «графом-решеткой» является решетка [math]\displaystyle{ r \times r \; }[/math], т.е. планарный граф с [math]\displaystyle{ r^2 \; }[/math] вершин, расположенных в виде квадратной решетки, ребра которой связывают горизонтально и вертикально смежные вершины. В случае двумерности со сжатием «граф-решетка» определяется следующим образом:

1. Для планарных графов и графов, свободных от миноров, с однократным пересечением, «граф-решетка» представляет собой решетку [math]\displaystyle{ r \times r \; }[/math], частично триангулированную дополнительными ребрами, сохраняющими планарность.

2. Для графов с ограниченным родом «граф-решетка» представляет собой такую частично триангулированную решетку [math]\displaystyle{ r \times r \; }[/math] с дополнительными ребрами («ручками») числом не более genus(G).

3. Для графов, свободных от апексных миноров, «граф-решетка» представляет собой решетку [math]\displaystyle{ r \times r \; }[/math] с дополнительными ребрами, такую, что каждая вершина инцидентна O(1) ребер, ведущих к неграничным вершинам решетки. (Здесь O(1) зависит от исключенного апексного графа).

Таким образом, двумерность со сжатием не определена для графов, свободных от H-миноров (или графов общего вида).

Примерами двумерных параметров могут служить количество вершин, диаметр и размеры различных структур – таких как разрывающее множество вершин, вершинное покрытие, минимальное паросочетание с максимальным весом, покрытие гранями, серия параметров для удаления вершин, доминирующее множество, доминирующее множество ребер, R-доминирующее множество, связное доминирующее множество, связное доминирующее множество ребер, связное R-доминирующее множество, невзвешенная метрическая задача коммивояжера (обход графа с посещением всех вершин) и хордальное дополнение (заполнение). Например, разрывающее множество вершин является [math]\displaystyle{ \Omega (r^2) \; }[/math]-минорно-двумерным (и, следовательно, сжато-двумерным), поскольку: (1) удаление или сжатие ребра сохраняет существующие разрывающие множества вершин; (2) любая вершина разрывающего множества вершин разрушает не более четырех квадратов решетки [math]\displaystyle{ r \times r \; }[/math], а поскольку всего имеется [math]\displaystyle{ (r - 1)^2 \; }[/math] квадратов, любое разрывающее множество вершин должно содержать [math]\displaystyle{ \Omega (r^2) \; }[/math] вершин. В [1, 3] можно ознакомиться с рассуждениями по поводу минорной двумерности и двумерности со сжатием для других параметров.

Основные результаты

Задача о двумерности строится на базе основополагающей теории о минорах графа Робертсона и Сеймура при помощи расширения некоторых математических результатов и построения новых алгоритмических инструментов. Несколько важных результатов в задачах о двумерности были получены на основе следующих комбинаторных утверждений. Первое из них связывает любой параметр двумерности с древесной шириной, второе – древесную ширину с минорами решетки.

Теорема 1 ([1, 8]). Если параметр P является g(r)-двумерным, то для любого графа G из семейства, ассоциированного с параметром P, [math]\displaystyle{ tw(G) = O(g^{-1} P(G))) \; }[/math]. В частности, если [math]\displaystyle{ g(r) = \Theta (r^2) \; }[/math], то граница превращается в [math]\displaystyle{ tw(G) = O( \sqrt{P(G)}) \; }[/math].

Теорема 2 ([8]). Для любого фиксированного графа H любой свободный от H-миноров граф с древесной шириной w имеет в качестве минора решетку [math]\displaystyle{ \Omega(w) \times \Omega(w) \; }[/math].

Двумя главными алгоритмическими подходами к задаче двумерности являются субэкспоненциальный алгоритм общего вида с фиксированными параметрами и общая схема аппроксимации с полиномиальным временем выполнения (PTAS):

Теорема 3 ([1, 8]). Рассмотрим g(r)-двумерный параметр P, который может быть вычислен на графе G за время [math]\displaystyle{ h(w)n^{O(1)} \; }[/math] при наличии древесной декомпозиции графа G шириной не более w. Существует алгоритм, вычисляющий P на любом графе G из соответствующего P класса графов с временем выполнения [math]\displaystyle{ [h(O(g^{-1} (k))) + 2^{O(g^{-1}(k))}] n^{O(1)} \; }[/math]. В частности, если [math]\displaystyle{ g(r) = \Theta (r^2) \; }[/math] и [math]\displaystyle{ h(w) = 2^{o(w^2)} \; }[/math], то это время выполнения является субэкспоненциальным относительно k.

Теорема 4 ([7]). Рассмотрим задачу двумерности, удовлетворяющую «свойству отделимости», определенному в [4, 7]. Предположим, что эта задача может быть решена на графе G с n вершинами за время f(n, tw(G)). Предположим также, что задача может быть аппроксимирована с коэффициентом [math]\displaystyle{ \alpha \; }[/math] за время g(n). Далее, для задачи двумерности со сжатием предположим далее, что оба этих алгоритма также применяются к «обобщенной форме» задачи, определенной в [4, 7]. Тогда существует алгоритм [math]\displaystyle{ (1 + \epsilon) \; }[/math]-аппроксимации задачи двумерности, время выполнения которого составляет [math]\displaystyle{ O(n f (n, O( \alpha^2 / \epsilon)) + n^3 g(n)) \; }[/math] для соответствующего класса графов.

Применение

Вышеприведенные теоремы широко применяются в комбинаторных и алгоритмических контекстах.

Применяя границу параметра и древесной ширины из теоремы 1 к параметру в виде количества вершин графа, можно доказать, что каждый граф, свободный от H-миноров, с n вершинами имеет древесную ширину [math]\displaystyle{ O( \sqrt{n}) }[/math], что служит (повторным) доказательством теоремы о сепараторах для графов, свободных от H-миноров. Применяя границу параметра и древесной ширины из теоремы 1 к параметру в виде диаметра графа, можно доказать более сильную форму отношения Эппштейна между диаметром и древесной шириной для графов, свободных от апексных миноров. (Далее можно показать, как еще больше усилить соотношение диаметра и древесной ширины до линейного [6]). Соотношение древесной ширины и решетки из теоремы 2 может использоваться для определения границы разрыва между полуцелым и дробным алгоритмами управления несколькими товарными потоками в свободных от H-миноров графах. Оно также дает O(1)-аппроксимацию древесной ширины для графов, свободных от H-миноров. Субэкспоненциальные алгоритмы с фиксированными параметрами из теоремы 3 подтверждают либо усиливают все подобные предыдущие результаты. Эти результаты также можно обобщить для получения алгоритмов с фиксированными параметрами на произвольных графах. В частности, схемы аппроксимации с полиномиальным временем выполнения (PTAS) из теоремы 4 позволяют получить первые PTAS для связного доминирующего множества и разрывающего множества вершин даже для планарных графов. Более детальное описание всех этих результатов можно найти в [4].

Открытые вопросы

В теории двумерности и родственных направлениях остаются нерешенными несколько комбинаторных и алгоритмических задач.

Можно ли обобщить теорему 2 о соотношении древесной ширины и решетки в свободных от H-миноров графах на произвольные графы с полиномиальным соотношением между древесной шириной и наибольшим минором-решеткой? (Наилучшее известное соотношение является экспоненциальным). Подобные полиномиальные обобщенные подходы были получены для случаев «графов-карт» и «графов высоких степеней» [9]. Удачные границы соотношения древесной ширины и решетки находят применение в минорно-двумерных задачах.

Можно ли обобщить алгоритмические результаты (теоремы 3 и 4) для решения задач о двумерности со сжатием, не ограничивающихся графами, свободными от апексных миноров? Известно, что лежащая в основе этих результатов теорема 1 не допускает обобщения [1]. Тем не менее, теорему 3 удалось обобщить для одной конкретной задачи о двумерности со сжатием – доминирующего множества [3].

Можно ли обобщить схемы аппроксимации с полиномиальным временем выполнения из теоремы 4 до алгоритмических задач более общего вида, не сопоставленных напрямую с двумерными параметрами? Один пример семейства подобных задач общего вида появляется при назначении вершинам и/или ребрам весов и необходимости вычислить, например, доминирующее множество с минимальным весом. Еще один пример такой задачи возникает при накладывании ограничений (например, на покрытие или доминирование) только на подмножества вершин и/или ребер. В качестве примеров таких задач можно привести алгоритмы построение дерева Штейнера и разрывающего множества вершин.

Другие открытые вопросы и подробное изложение перечисленных можно найти в [4].

См. также

• Схемы аппроксимации для задач с планарными графами
• Путевая ширина графа
• Древесная ширина графа

Литература

1. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discret. Math. 18(3), 501-511 (2004)

2. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33^7 (2005)

3. Demaine, E.D., Fomin, F.V., Hajiaghayi, M.,Thilikos, D.M.: Subexponential parametrized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM 52(6), 866-893 (2005)

4. Demaine, E.D., Hajiaghayi, M.:The bidimensionality theory and its algorithmic applications. Comput. J. To appear

5. Demaine, E.D., Hajiaghayi, M.: Diameter and treewidth in minor-closed graph families, revisited. Algorithmica 40(3),211-215(2004)

6. Demaine, E.D., Hajiaghayi, M.: Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA'04), January 2004, pp. 833-842 (2004)

7. Demaine, E.D., Hajiaghayi, M.: Bidimensionality: New connections between FPT algorithms and PTASs. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 590-601. Vancouver, January (2005)

8. Demaine, E.D., Hajiaghayi, M.: Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 682-689. Vancouver, January (2005)

9. Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.: Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction. In: Proceedings of the 17th Annual International Symposium on Algorithms and Computation, Calcutta, India, December 2006. Lecture Notes in Computer Science, vol.4288, pp. 3-15(2006)

10. Demaine, E.D., Hajiaghayi, M., Nishimura, N., Ragde, P., Thilikos, D.M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69(2),166-195(2004)

11. Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica41(4),245-267(2005)

12. Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: The bidimensional theory of bounded-genus graphs. SIAM J. Discret. Math. 20(2), 357-371 (2006)