Разрезающее циклы множество вершин
В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа. Задача о разрезающем циклы множестве вершин является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС.
Определение[править | править код]
Задача о разрезающем циклы множестве вершин — это следующая задача разрешимости:
- Дано: (Неориентированный или ориентированный) граф и положительное число .
- Вопрос: Существует ли подмножество , для которого , такой, что с удалёнными вершинами, принадлежащими , не содержит циклов?
Граф , оставшийся после удаления из графа вершин, принадлежащих множеству , является порождённым лесом (для неориентированных графов, или порождённым направленным ациклическим графом для ориентированных графов). Таким образом, поиск минимального разрезающего цикла множество вершин в графе эквивалентен поиску максимального порождённого леса (соответственно, максимального порождённого ациклического графа в случае ориентированных графов).
![{\displaystyle G[V\setminus X]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1166277c8d75dce9d8ea1f3ede58bd79c083211d)
NP-трудность[править | править код]
Карп[1] показал, что задача о разрезающем циклы множестве вершин для ориентированных графов является NP-полной. Задача остаётся NP-полной для направленных графов с максимальной степенью входящих и исходящих дуг, равной двум, и для ориентированных пленарных графов с максимальной степенью входящих и исходящих дуг, равной трём[2]. Из приведения Карпа также следует NP-полнота задачи о разрезающем циклы множестве вершин на неориентированных графов, и задача остаётся NP-трудной на графах с максимальной степенью четыре. Задача о разрезающем циклы множестве вершин может быть решена за полиномиального времени на графах с максимальной степенью, не превосходящей трёх[3][4].
Заметим, что задача удаления как можно меньшего числа рёбер для разрыва циклов (в неориентированном графе) эквивалентна нахождению остовного дерева, и эта задача может быть выполнена за полиномиальное время. В противоположность этому задача удаления рёбер из ориентированного графа с целью сделать его ациклическим, то есть задача о разрезающем циклы наборе дуг, является NP-полной[1].
Точные алгоритмы[править | править код]
Соответствующая NP-полная оптимизационная задача нахождения размера минимального разрезающего циклы множества вершин может быть решена за время O(1,7347n), где n — число вершин в графе [5]. Фактически этот алгоритм находит максимальный порождённый лес и дополнение этого леса будет искомым набором вершин. Число минимальных разрезающих циклы множеств вершин ограничено O(1,8638n)[6]. Задача о минимальном разрезающем циклы множестве для ориентированного графа может быть решена за время O*(1,9977n), где n — число вершин в данном ориентированном графе[7]. Параметризованные версии ориентированной и неориентированной задач фиксированно-параметрически разрешимы[англ.][8].
Приближение[править | править код]
Задача является APX-полной, что прямо следует из APX-сложности задачи о вершинном покрытии[9] и существования аппроксимации, сохраняющей L-приведение из задачи о вершинном покрытии к этой задаче[1]. Лучший известный алгоритм для неориентированных графов имеет коэффициент два[10].
Границы[править | править код]
Согласно теореме Эрдёша — Поза размер минимального разрезающего циклы множества вершин ограничен логарифмическим множителем от максимального числа вершинно-непересекающихся циклов в заданном графе[11].
Приложения[править | править код]
В операционных системах разрезающее циклы множество вершин играет заметную роль в обнаружении взаимных блокировок (deadlock). В графе ожидания операционной системы каждый ориентированный цикл соответствует взаимной блокировке. Чтобы выйти из всех взаимных блокировок, некоторые блокированные процессы должны быть прерваны. Минимальное разрезающее циклы множество вершин в графе соответствует минимальному числу процессов, которые следует прервать[12]
Кроме того, разрезающее циклы множество вершин имеет приложение в разработке СБИС[13].
Примечания[править | править код]
- ↑ 1 2 3 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.
 | Для улучшения этой статьи желательно:
|