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

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

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

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

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

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