Двумерность

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

Теория двумерности включает обобщенные техники разработки эффективных алгоритмов с фиксированными параметрами и алгоритмов аппроксимации для широкого круга NP-полных графовых задач на широком круг графов. Эта теория применяется к графовым задачам, которые являются «двумерными» в следующем смысле: (1) значение решения для графа, представленного в виде решетки k _ k, и подобных ему графов растет вместе с k, обычно как (k2); (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-миноров, если H … C. В более общем смысле, термин «не содержит H-миноров» относится к любому классу графов, замкнутому относительно операции взятия минора, который не включает некоторый фиксированный граф H. Граф с однократным пересечением представляет собой минор графа, который может быть изображен на плоскости так, что в нем будет пересекаться не более одной пары ребер. Класс графов, замкнутый относительно операции взятия минора, не содержит миноров с однократным пересечением, если из него исключен фиксированный граф с однократным пересечением. Апексным графом называется граф, который становится планарным при удалении из него некоторой вершины. Класс графов является классом без апексных миноров, если из него исключен некоторый фиксированный апексный граф.

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

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