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

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

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

Параметр является g(r)-двумерным (или просто двумерным)если он равен не менее чем g(r) в графе-решетке размером r x r и если он не повышается при взятии миноров g(r)(-минорно-двумерный) либо выполнении сжатий (g(r)-сжато-двумерный). Точное определение «графа-решетки» зависит от класса допустимых графов и от того, рассматривается ли минорная двумерность или двумерность сжатия. Для случая минорной двумерности и для любого класса графов, не содержащего H-миноров, «графом-решеткой» является решетка r x r, т.е. планарный граф с r2 вершин, расположенных в виде квадратной решетки, ребра которой связывают горизонтально и вертикально смежные вершины. В случае двумерности сжатия «граф-решетка» определяется следующим образом:

1. Для планарных графов и графов, не содержащих миноров с однократным пересечением, «граф-решетка» представляет собой решетку r x r, частично триангулированную дополнительными ребрами, сохраняющими планарность.

3. Для графов, не содержащих апексных миноров, «граф-решетка» представляет собой решетку r x r с дополнительными ребрами, такую, что каждая вершина инцидентна O(1) ребер, ведущих к неграничным вершинам решетки. (Здесь O(1) зависит от исключенного апексного графа).

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

Примерами двумерных параметров могут служить количество вершин, диаметр и размеры различных структур – таких как разрывающее множество вершин, вершинное покрытие, минимальное паросочетание с максимальным весом, покрытие гранями, серия параметров для удаления вершин, доминирующее множество, доминирующее множество ребер, R-доминирующее множество, связное доминирующее множество, связное доминирующее множество ребер, связное R-доминирующее множество, невзвешенная метрическая задача коммивояжера (обход графа с посещением всех вершин) и хордальное дополнение (заполнение). Например, разрывающее множество вершин является £?(r2)-минорно-двумерным (и, следовательно, сжато-двумерным), поскольку: (1) удаление или сжатие ребра сохраняет существующие разрывающие множества вершин; (2) любая вершина разрывающего множества вершин разрушает не более четырех квадратов решетки r x r, а поскольку в ней имеется (r — 1)2 квадратов, любое разрывающее множество вершин должно содержать Q(r2) вершин. В [1, 3] можно ознакомиться с рассуждениями по поводу минорной двумерности и двумерности сжатия для других параметров.

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

Теорема 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)) для соответствующего класса графов.