Разрывающее множество вершин на неориентированном графе: различия между версиями

Дано: неориентированный граф <math>G = (V, E) \;</math> и целое число <math>k \ge 0 \;</math>.

Требуется: найти [[Feedback vertex set|разрывающее множество вершин]] <math>F \subseteq V \;</math>, <math>|F| \le k \;</math>, такое, что каждый цикл в графе G содержит не менее одной вершины из F. (В результате удаления всех вершин F из G граф превращается в лес).

Карп [11] показал, что эта задача является NP-полной. Лунд и Янакаккис [12] доказали, что существует некоторая константа <math>\epsilon > 0 \;</math>, такая, что аппроксимация версии оптимизации UFVS с коэффициентом <math>1 + \epsilon \;</math> является NP-полной задачей. Лучший известный на данный момент алгоритм аппроксимации с полиномиальным временем выполнения имеет коэффициент 2 [1, 4]. Беккер и др. [3] предложили простой и элегантный рандомизированный алгоритм, решающий задачу UFVS за время <math>O(c \cdot 4^k \cdot kn) \;</math> на графе с n вершинами и m ребрами при помощи нахождения разрывающего множества вершин размера k с вероятностью не менее <math>1 - (1 - 4^{-k})^{c4^k} \;</math> для произвольной константы c. Точный алгоритм решения задачи UFVS с временем выполнения <math>O(1,7548^n) \;</math> недавно разработали Фомин и др. [9]. В контексте параметризованной сложности [8, 13] Бодлендер [5], а также Дауни и Феллоуз [7] первыми показали, что задача разрешима при помощи алгоритмов с фиксированными параметрами, т.е. что комбинаторный взрыв при ее решении может быть ограничен параметром k. Наилучший известный на данный момент алгоритм решения задачи UFVS с фиксированным параметром выполняется за время <math>O(c^k \cdot mn) \;</math> для константы c [6, 10] (в [6] представлен анализ наилучшего времени выполнения, имеющего место при значении константы c = 10,567). Этот алгоритм будет рассмотрен далее.