Двумерность: различия между версиями

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

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

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

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

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

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

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

Теорема 4 ([7]). Рассмотрим задачу двумерности, удовлетворяющую «свойству отделимости», определенному в [4, 7]. Предположим, что эта задача может быть решена на графе G с n вершинами за время f(n; tw(G)). Предположим также, что задача может быть аппроксимирована с коэффициентом a за время g(n). Далее, для задачи двумерности со сжатием предположим далее, что оба этих алгоритма также применяются к «обобщенной форме» задачи, определенной в [4, 7]. Тогда существует алгоритм (1 + e)-аппроксимации задачи двумерности, время выполнения которого составляет O(nf(n; O(a2/e)) + n3g(n)) для соответствующего класса графов.

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

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

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

* ''[[Схемы аппроксимации для задач с планарными графами]]

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)

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