Разрезающее циклы множество вершин

В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа. Задача о разрезающем циклы множестве вершин➤ является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС.

Определение

Задача о разрезающем циклы множестве вершин — это следующая задача разрешимости:

Дано: (Неориентированный или ориентированный) граф ${\displaystyle G=(V,E)}$ и положительное число ${\displaystyle k}$.

Вопрос: Существует ли подмножество ${\displaystyle X\subseteq V}$, для которого ${\displaystyle |X|\leq k}$, такой, что ${\displaystyle G}$ с удалёнными вершинами, принадлежащими ${\displaystyle X}$, не содержит циклов?

Граф ${\displaystyle G[V\setminus X]}$, оставшийся после удаления из графа ${\displaystyle G}$ вершин, принадлежащих множеству ${\displaystyle X}$, является порождённым лесом (для неориентированных графов, или порождённым направленным ациклическим графом для ориентированных графов). Таким образом, поиск минимального разрезающего циклы множества вершин в графе эквивалентен поиску максимального порождённого леса (соответственно, максимального порождённого ациклического графа в случае ориентированных графов).

NP-трудность

Карп[1] показал, что задача о разрезающем циклы множестве вершин для ориентированных графов является NP-полной. Задача остаётся NP-полной для направленных графов с максимальной степенью входящих и исходящих дуг, равной двум, и для ориентированных пленарных графов с максимальной степенью входящих и исходящих дуг, равной трём[2]. Из приведения Карпа также следует NP-полнота задачи о разрезающем циклы множестве вершин на неориентированных графах, и задача остаётся NP-трудной на графах с максимальной степенью четыре. Задача о разрезающем циклы множестве вершин может быть решена за полиномиального времени на графах с максимальной степенью, не превосходящей трёх[3][4].

Заметим, что задача удаления как можно меньшего числа рёбер для разрыва циклов (в неориентированном графе) эквивалентна нахождению остовного дерева, и эта задача может быть выполнена за полиномиальное время. В противоположность этому задача удаления рёбер из ориентированного графа с целью сделать его ациклическим, то есть задача о разрезающем циклы наборе дуг, является NP-полной[1].

Точные алгоритмы

Соответствующая NP-полная оптимизационная задача нахождения размера минимального разрезающего циклы множества вершин может быть решена за время O(1,7347^n), где n — число вершин в графе [5]. Фактически этот алгоритм находит максимальный порождённый лес и дополнение этого леса будет искомым набором вершин. Число минимальных разрезающих циклы множеств вершин ограничено O(1,8638^n)[6]. Задача о минимальном разрезающем циклы множестве для ориентированного графа может быть решена за время O*(1,9977^n), где n — число вершин в данном ориентированном графе[7]. Параметризованные версии ориентированной и неориентированной задач фиксированно-параметрически разрешимы^[англ.][8].

Приближение

Задача является APX-полной, что прямо следует из APX-сложности задачи о вершинном покрытии[9] и существования аппроксимации, сохраняющей L-приведение из задачи о вершинном покрытии к этой задаче[1]. Лучший известный алгоритм для неориентированных графов имеет коэффициент два[10].

Границы

Согласно теореме Эрдёша — Поза размер минимального разрезающего циклы множества вершин ограничен логарифмическим множителем от максимального числа вершинно-непересекающихся циклов в заданном графе[11].

Приложения

В операционных системах разрезающее циклы множество вершин играет заметную роль в обнаружении взаимных блокировок (deadlock). В графе ожидания операционной системы каждый ориентированный цикл соответствует взаимной блокировке. Чтобы выйти из всех взаимных блокировок, некоторые блокированные процессы должны быть прерваны. Минимальное разрезающее циклы множество вершин в графе соответствует минимальному числу процессов, которые следует прервать[12]

Кроме того, разрезающее циклы множество вершин имеет приложение в разработке СБИС[13].

Примечания

1. Karp, 1972.
2. Неопубликованный результат, принадлежащий Гарей и Джонсону (Garey, Johnson), см. Garey, Johnson, 1979: GT7
3. Ueno, Kajitani, Gotoh, 1988.
4. Li, Liu, 1999.
5. Fomin, Villanger, 2010.
6. Fomin, Gaspers, Pyatkin, Razgon, 2008.
7. Razgon, 2007.
8. Chen, Liu, Lu, O'Sullivan, Razgon, 2008.
9. Dinur, Safra, 2005.
10. Becker, Geiger, 1996. См. также Bafna, Berman, Fujito, 1999 для альтернативного аппроксимационного алгоритма с тем же коэффициентом.
11. Erdős, Pósa, 1965.
12. Silberschatz, Galvin, Gagne, 2008.
13. Festa, Pardalos, Resende, 2000.

Литература

Исследовательские статьи и книги

• Vineet Bafna, Piotr Berman, Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem // SIAM Journal on Discrete Mathematics. — 1999. — Т. 12, вып. 3. — С. 289–297 (electronic). — doi:10.1137/S0895480196305124..
• Ann Becker, Reuven Bar-Yehuda, Dan Geiger. Randomized algorithms for the loop cutset problem // Journal of Artificial Intelligence Research. — 2000. — Т. 12. — С. 219–234. — doi:10.1613/jair.638. — arXiv:1106.0225.
• Ann Becker, Dan Geiger. Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. // Artificial Intelligence. — 1996. — Т. 83, вып. 1. — С. 167–188. — doi:10.1016/0004-3702(95)00004-6.
• Yixin Cao, Jianer Chen, Yang Liu. Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Bergen, Norway, June 21-23, 2010 / Haim Kaplan. — 2010. — Т. 6139. — С. 93–104. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-13731-0_10.
• Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, Yngve Villanger. Improved algorithms for feedback vertex set problems // Journal of Computer and System Sciences. — 2008. — Т. 74, вып. 7. — С. 1188–1198. — doi:10.1016/j.jcss.2008.05.002.
• Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem // Journal of the ACM. — 2008. — Т. 55, вып. 5. — doi:10.1145/1411509.1411511.
• Irit Dinur, Samuel Safra. On the hardness of approximating minimum vertex cover // Annals of Mathematics. — 2005. — Т. 162, вып. 1. — С. 439–485. — doi:10.4007/annals.2005.162.439.
• Paul Erdős, Lajos Pósa. On independent circuits contained in a graph // Canadian Journal of Mathematics. — 1965. — Т. 17. — С. 347–352. — doi:10.4153/CJM-1965-035-8.
• Fedor V. Fomin, Serge Gaspers, Artem Pyatkin, Igor Razgon. On the minimum feedback vertex set problem: exact and enumeration algorithms. // Algorithmica. — 2008. — Т. 52, вып. 2. — С. 293–307. — doi:10.1007/s00453-007-9152-0.
• Fedor V. Fomin, Yngve Villanger. Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010). — 2010. — Т. 5. — С. 383–394. — (Leibniz International Proceedings in Informatics (LIPIcs)). — doi:10.4230/LIPIcs.STACS.2010.2470.
• Richard M. Karp. Proc. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.. — New York: Plenum, 1972. — С. 85–103.
• Deming Li, Yanpei Liu. A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph // Acta Mathematica Scientia. — 1999. — Т. 19, вып. 4. — С. 375–381.
• I. Razgon. Proceedings of the 10th Italian Conference on Theoretical Computer Science / Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura. — World Scientific, 2007. — С. 70–81.
• Shuichi Ueno, Yoji Kajitani, Shin'ya Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three // Discrete Mathematics. — 1988. — Т. 72, вып. 1—3. — С. 355–360. — doi:10.1016/0012-365X(88)90226-9.

Учебники и обзорные статьи

• P. Festa, P. M. Pardalos, M.G.C. Resende. Handbook of Combinatorial Optimization, Supplement vol. A / D.-Z. Du, P. M. Pardalos. — Kluwer Academic Publishers, 2000. — С. 209–259.
• Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W.H. Freeman, 1979. — ISBN 0-7167-1045-5.
• Abraham Silberschatz, Peter Baer Galvin, Greg Gagne. Operating System Concepts. — John Wiley & Sons. Inc, 2008. — ISBN 978-0-470-12872-5.