Feedback vertex set
In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph. The feedback vertex set problem is an NP-complete problem in computational complexity theory. It was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.
The decision problem is as follows:
- INSTANCE: An (undirected or directed) graph and a positive integer .
- QUESTION: Is there a subset with such that with the vertices from deleted is cycle-free?
The graph that remains after removing from is an induced forest (resp. an induced directed acyclic graph in the case of directed graphs). Thus, finding a minimum feedback vertex set in a graph is equivalent to finding a maximum induced forest (resp. maximum induced directed acyclic graph in the case of directed graphs).
Karp (1972) showed that the feedback vertex set problem for directed graphs is NP-complete. The problem remains NP-complete on directed graphs with maximum in-degree and out-degree two, and on directed planar graphs with maximum in-degree and out-degree three. Karp's reduction also implies the NP-completeness of the feedback vertex set problem on undirected graphs, where the problem stays NP-hard on graphs of maximum degree four. The feedback vertex set problem can be solved in polynomial time on graphs of maximum degree at most three.
Note that the problem of deleting as few edges as possible to make the graph cycle-free is equivalent to finding a spanning tree, which can be done in polynomial time. In contrast, the problem of deleting edges from a directed graph to make it acyclic, the feedback arc set problem, is NP-complete.
The corresponding NP optimization problem of finding the size of a minimum feedback vertex set can be solved in time O(1.7347n), where n is the number of vertices in the graph. This algorithm actually computes a maximum induced forest, and when such a forest is obtained, its complement is a minimum feedback vertex set. The number of minimal feedback vertex sets in a graph is bounded by O(1.8638n). The directed feedback vertex set problem can still be solved in time O*(1.9977n), where n is the number of vertices in the given directed graph. The parameterized versions of the directed and undirected problems are both fixed-parameter tractable.
The problem is APX-complete, which directly follows from the APX-completeness of the vertex cover problem, and the existence of an approximation preserving L-reduction from the vertex cover problem to it. The best known approximation algorithm on undirected graphs is by a factor of two, based on the Becker-Geiger theorem.
In operating systems, feedback vertex sets play a prominent role in the study of deadlock recovery. In the wait-for graph of an operating system, each directed cycle corresponds to a deadlock situation. In order to resolve all deadlocks, some blocked processes have to be aborted. A minimum feedback vertex set in this graph corresponds to a minimum number of processes that one needs to abort.
- unpublished results due to Garey and Johnson, cf. Garey & Johnson (1979): GT7
- Ueno, Kajitani & Gotoh (1988); Li & Liu (1999)
- Karp (1972)
- Fomin & Villanger (2010)
- Fomin et al. (2008).
- Razgon (2007).
- Chen et al. (2008).
- Dinur & Safra 2005
- Becker & Geiger (1996).
- Erdős & Pósa (1965).
- Silberschatz, Galvin & Gagne (2008).
- Festa, Pardalos & Resende (2000).
- Becker, Ann; Bar-Yehuda, Reuven; Geiger, Dan (2000), "Randomized algorithms for the loop cutset problem", Journal of Artificial Intelligence Research 12: 219–234, arXiv:1106.0225, doi:10.1613/jair.638, MR 1765590
- Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.", Artificial Intelligence 83 (1): 167–188, doi:10.1016/0004-3702(95)00004-6
- Cao, Yixin; Chen, Jianer; Liu, Yang (2010), "On feedback vertex set: new measure and new structures", in Kaplan, Haim, Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Bergen, Norway, June 21-23, 2010, Lecture Notes in Computer Science 6139, pp. 93–104, doi:10.1007/978-3-642-13731-0_10
- Chen, Jianer; Fomin, Fedor V.; Liu, Yang; Lu, Songjian; Villanger, Yngve (2008), "Improved algorithms for feedback vertex set problems", Journal of Computer and System Sciences 74 (7): 1188–1198, doi:10.1016/j.jcss.2008.05.002, MR 2454063
- Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM 55 (5), Art. 21, doi:10.1145/1411509.1411511, MR 2456546
- Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover", Annals of Mathematics, Second Series 162 (1): 439–485, doi:10.4007/annals.2005.162.439, MR 2178966
- Erdős, Paul; Pósa, Lajos (1965), "On independent circuits contained in a graph", Canadian Journal of Mathematics 17: 347–352, doi:10.4153/CJM-1965-035-8
- Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008), "On the minimum feedback vertex set problem: exact and enumeration algorithms.", Algorithmica 52 (2): 293–307, doi:10.1007/s00453-007-9152-0
- Fomin, Fedor V.; Villanger, Yngve (2010), "Finding induced subgraphs via minimal triangulations", Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), Leibniz International Proceedings in Informatics (LIPIcs) 5, pp. 383–394, doi:10.4230/LIPIcs.STACS.2010.2470
- Karp, Richard M. (1972), "Reducibility Among Combinatorial Problems", Proc. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103
- Li, Deming; Liu, Yanpei (1999), "A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph", Acta Mathematica Scientia 19 (4): 375–381, MR 1735603
- Razgon, I. (2007), "Computing minimum directed feedback vertex set in O*(1.9977n)", in Italiano, Giuseppe F.; Moggi, Eugenio; Laura, Luigi, Proceedings of the 10th Italian Conference on Theoretical Computer Science, World Scientific, pp. 70–81
- Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three", Discrete Mathematics 72 (1-3): 355–360, doi:10.1016/0012-365X(88)90226-9, MR 975556
Textbooks and survey articles
- Festa, P.; Pardalos, P. M.; Resende, M.G.C. (2000), "Feedback set problems", in Du, D.-Z.; Pardalos, P. M., Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, pp. 209–259
- Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A1.1: GT7, p. 191, ISBN 0-7167-1045-5
- Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5