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

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

ОпределениеПравить

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

Дано: (Неориентированный или ориентированный) граф

\text{[math]}

G=(V,E)

и положительное число

\text{[math]}

k

.

Вопрос: Существует ли подмножество

\text{[math]}

X\subseteq V

, для которого

\text{[math]}

|X|\leq k

, такой, что

\text{[math]}

G

с удалёнными вершинами, принадлежащими

\text{[math]}

X

, не содержит циклов?

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

NP-трудностьПравить

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

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

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

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

ПриближениеПравить

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

ГраницыПравить

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

ПриложенияПравить

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

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

ПримечанияПравить

↑ ¹ ² ³ Karp, 1972.
↑ Неопубликованный результат, принадлежащий Гарей и Джонсону (Garey, Johnson), см. Garey, Johnson, 1979: GT7
↑ Ueno, Kajitani, Gotoh, 1988.
↑ Li, Liu, 1999.
↑ Fomin, Villanger, 2010.
↑ Fomin, Gaspers, Pyatkin, Razgon, 2008.
↑ Razgon, 2007.
↑ Chen, Liu, Lu, O'Sullivan, Razgon, 2008.
↑ Dinur, Safra, 2005.
↑ Becker, Geiger, 1996. См. также Bafna, Berman, Fujito, 1999 для альтернативного аппроксимационного алгоритма с тем же коэффициентом.
↑ Erdős, Pósa, 1965.
↑ Silberschatz, Galvin, Gagne, 2008.
↑ 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.

[_9e0834b4bef35f12-1] ¹ ² ³ Karp, 1972.

[2] Неопубликованный результат, принадлежащий Гарей и Джонсону (Garey, Johnson), см. Garey, Johnson, 1979: GT7

[_2bbf63e620ca85aa-3] Ueno, Kajitani, Gotoh, 1988.

[_ddd8422cbf59f21c-4] Li, Liu, 1999.

[_18624ddc95c638cb-5] Fomin, Villanger, 2010.

[_61eb104c52a70054-6] Fomin, Gaspers, Pyatkin, Razgon, 2008.

[_3662ba9ea27c0197-7] Razgon, 2007.

[_53b89a67396e1595-8] Chen, Liu, Lu, O'Sullivan, Razgon, 2008.

[_e4f4fa1b2c3eef7d-9] Dinur, Safra, 2005.

[10] Becker, Geiger, 1996. См. также Bafna, Berman, Fujito, 1999 для альтернативного аппроксимационного алгоритма с тем же коэффициентом.

[_6009d4474b7aec1c-11] Erdős, Pósa, 1965.

[_9022698e841acb78-12] Silberschatz, Galvin, Gagne, 2008.

[_67bd90494c524a04-13] Festa, Pardalos, Resende, 2000.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]