Разрывающее множество вершин на неориентированном графе

Ключевые слова и синонимы

Обход нечетного цикла

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

Задача нахождения разрывающего множества вершин на неориентированном графе (The UNDIRECTED FEEDBACK VERTEX SET, UFVS) определяется следующим образом.

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

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

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

Основные результаты

Алгоритм решения задачи UFVS за время [math]\displaystyle{ O(c^k \cdot mn) \; }[/math] основан на так называемой технике «итеративного сжатия», введенной Ридом и др. [14]. Основная идея этой техники проста, но эффективна: для вывода алгоритма с фиксированным параметром для задачи минимизации достаточно задать «подпрограмму сжатия» с фиксированным параметром, которая для решения размера (k + 1) либо доказывает, что решения размера k не существует, либо строит такое решение. Начиная с тривиального экземпляра и итеративно применяя подпрограмму сжатия линейное количество раз к экземплярам большего размера, получаем алгоритм решения задачи с фиксированным параметром. Главная проблема при применении этой техники к задаче UFVS заключается в том, чтобы показать, что такая подпрограмма сжатия с фиксированным параметром существует.

Подпрограмма сжатия, представленная в [6, 10], работает следующим образом:

1 Рассмотрим все возможные разбиения (X, Y), имеющие размер (k + 1), для разрывающего множества вершин F с [math]\displaystyle{ |X| \le k \; }[/math] в предположении, что множество X полностью содержится в новом разрывающем множестве F' размера k и что [math]\displaystyle{ Y \cap F' = \empty \; }[/math].

2 Для каждого разбиения (X, Y), в случае, если вершины из Y порождают циклы, ответ для этого разбиения будет отрицательным; в противном случае следует удалить вершины из X. После этого необходимо применить следующие правила редукции данных к оставшемуся графу:

• Удалить вершины степени 1.

• Если существует вершина степени 2 с двумя соседями [math]\displaystyle{ v_1 \; }[/math] и [math]\displaystyle{ v_2 \; }[/math], где [math]\displaystyle{ v_1 \notin Y \; }[/math] или [math]\displaystyle{ v_2 \notin Y \; }[/math], то удалить v и соединить [math]\displaystyle{ v_1 \; }[/math] и [math]\displaystyle{ v_2 \; }[/math]. Если при этом создается второе параллельное ребро между [math]\displaystyle{ v_1 \; }[/math] и [math]\displaystyle{ v_2 \; }[/math], удалить вершину [math]\displaystyle{ v_1 \; }[/math] плюс [math]\displaystyle{ v_2 \; }[/math], не принадлежащую к Y, и добавить ее к любому разрывающему множеству вершин для сокращенного экземпляра.

Наконец, исчерпывающим образом для каждого множества вершин S сокращенного графа, размер которого не превышает k — |X|, проверим, можно ли добавить S к X для образования разрывающего множества вершин входного графа. Если такое множество вершин существует, вывести его вместе с X в качестве нового разрывающего множества вершин размера k.

Корректность подпрограммы сжатия следует из ее прямолинейной природы и из корректности двух правил редукции данных, доказать которую несложно. Важнее показать, что время выполнения подпрограммы сжатия составляет [math]\displaystyle{ O(c^k \cdot m) \; }[/math]: существует [math]\displaystyle{ 2^k + 1 \; }[/math] разбиений множества F на вышеупомянутые подмножества (X, Y); можно показать, что для каждого разбиения сокращенный граф после выполнения правил редукции данных имеет не более [math]\displaystyle{ d \cdot k \; }[/math] вершин для константного значения d; в противном случае для этого разбиения не существует разрывающего множества вершин размера k. Таким образом, время выполнения составляет [math]\displaystyle{ O(c^k \cdot m) \; }[/math]. Более детальное доказательство границы размера [math]\displaystyle{ d \cdot k \; }[/math] см. в [6, 10].

Для входного графа G с множеством вершин [math]\displaystyle{ \{ v_1, ..., v_n \} \; }[/math] алгоритм с фиксированным параметром из работ [6, 10] решает задачу UFVS путем итеративного рассмотрения подграфов [math]\displaystyle{ G_i := G[ \{v_1, ..., v_i \} ] \; }[/math]. Для i = 1 оптимальное разрывающее множество вершин является пустым. Предположим, что в случае i > 1 оптимальное разрывающее множество вершин [math]\displaystyle{ X_i \; }[/math] для [math]\displaystyle{ G_i \; }[/math] известно. Очевидно, что [math]\displaystyle{ X_i \cup \{ v_{i+1} \} \; }[/math] является искомым множеством для [math]\displaystyle{ G_{i+1} \; }[/math]. Используя подпрограмму сжатия, алгоритм за время [math]\displaystyle{ O(c^k \cdot m) \; }[/math] может определить, является ли [math]\displaystyle{ X_i \cup \{ v_{i+1} \} \; }[/math] оптимальным разрывающим множеством вершин для [math]\displaystyle{ G_{i+1} \; }[/math], и в случае, если оно таковым не является, вычислить оптимальное разрывающее множество вершин для [math]\displaystyle{ G_{i+1} \; }[/math]. Таким образом, в случае i = n мы получаем оптимальное разрывающее множество вершин для графа G за время [math]\displaystyle{ O(c^k \cdot mn) \; }[/math].

Теорема 1. Задачу нахождения разрывающего множества вершин на неориентированном графе можно решить за время [math]\displaystyle{ O(c^k \cdot mn) \; }[/math] для константного значения c.

Применение

Задача нахождения разрывающего множества вершин на неориентированном графе имеет огромное значение для комбинаторной оптимизации. Типичным примером может служить разработка комбинаторных схем [1]. Приложения в области задач на удовлетворение ограничений и баейсовского вывода см. в работе Бар-Йехуды и др. [2].

Открытые вопросы

До сих пор не исследована эффективность описанного алгоритма на практике. Еще одно перспективное направление исследований заключается в улучшении границы времени выполнения, приведенной в теореме 1. Наконец, долгое время остается нерешенным вопрос, является ли задача нахождения разрывающего множества на ориентированном графе разрешимой с фиксированным параметром. Ответ на этот вопрос станет серьезным прорывом в данной области.

Литература

1. Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discret. Math. 3(2), 289-297 (1999)

2. Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. 27(4), 942-959 (1998)

3. Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the Loop Cutset problem. J. Artif. Intell. Res. 12, 219-234 (2000)

4. Becker, A., Geiger, D.: Approximation algorithms for the Loop Cutset problem. In: Proc. 10th Conference on Uncertainty in Artificial Intelligence, pp. 60-68. Morgan Kaufman, San Fransisco (1994)

5. Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comp. Sci. 5(1),59-68(1994)

6. Dehne, F., Fellows, M.R., Langston, M.A., Rosamond, F., Stevens, K.: An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem. In: Proc. 11th COCOON. LNCS, vol. 3595, pp. 859-869. Springer, Berlin (2005). Long version to appear in: J. Discret. Algorithms

7. Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. Congres. Numerant.87,161-187 (1992)

8. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)

9. Fomin, F.V., Gaspers, S., Pyatkin, A.V.: Finding a minimum feedback vertex set in time O(1.7548n). In: Proc. 2th IWPEC. LNCS, vol.4196, pp. 184-191. Springer, Berlin (2006)

10. Guo, J., Gramm, J., HCiffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for Feedback Vertex Set and Edge Bipartization. J. Comp. Syst. Sci. 72(8), 1386-1396 (2006)

11. Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85-103. Plenum Press, New York (1972)

12. Lund, C., Yannakakis, M.: The approximation of maximum subgraph problems. In: Proc. 20th ICALP. LNCS, vol. 700, pp.40-51. Springer, Berlin (1993)

13. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)

14. Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299-301 (2004)