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.

Definition

The decision problem is as follows:

INSTANCE: An (undirected or directed) graph $G=(V,E)$ and a positive integer $k$.

QUESTION: Is there a subset $X\subseteq V$ with $|X|\leq k$ such that $G$ with the vertices from $X$ deleted is cycle-free?

The graph $G[V\setminus X]$ that remains after removing $X$ from $G$ 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).

NP-hardness

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.^[1] 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.^[2]

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.^[3]

Exact algorithms

The corresponding NP optimization problem of finding the size of a minimum feedback vertex set can be solved in time O(1.7347ⁿ), where n is the number of vertices in the graph.^[4] 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.8638ⁿ).^[5] The directed feedback vertex set problem can still be solved in time O*(1.9977ⁿ), where n is the number of vertices in the given directed graph.^[6] The parameterized versions of the directed and undirected problems are both fixed-parameter tractable.^[7]

Approximation

The problem is APX-complete, which directly follows from the APX-completeness of the vertex cover problem,^[8] and the existence of an approximation preserving L-reduction from the vertex cover problem to it.^[3] The best known approximation algorithm on undirected graphs is by a factor of two.^[9]

Bounds

According to the Erdős–Pósa theorem, the size of a minimum feedback vertex set is within a logarithmic factor of the maximum number of vertex-disjoint cycles in the given graph.^[10]

Applications

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.^[11]

Furthermore, the feedback vertex set problem has applications in VLSI chip design.^[12]

Notes

1. unpublished results due to Garey and Johnson, cf. Garey & Johnson (1979): GT7
2. Ueno, Kajitani & Gotoh (1988); Li & Liu (1999)
3. Karp (1972)
4. Fomin & Villanger (2010)
5. Fomin et al. (2008).
6. Razgon (2007).
7. Chen et al. (2008).
8. Dinur & Safra 2005
9. Becker & Geiger (1996). See also Bafna, Berman & Fujito (1999) for an alternative approximation algorithm with the same approximation ratio.
10. Erdős & Pósa (1965).
11. Silberschatz, Galvin & Gagne (2008).
12. Festa, Pardalos & Resende (2000).

References

Research articles

• Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro (1999), "A 2-approximation algorithm for the undirected feedback vertex set problem", SIAM Journal on Discrete Mathematics, 12 (3): 289–297 (electronic), doi:10.1137/S0895480196305124, MR 1710236.
• 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" (PDF), 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" (PDF), 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.9977ⁿ)", in Italiano, Giuseppe F.; Moggi, Eugenio; Laura, Luigi, Proceedings of the 10th Italian Conference on Theoretical Computer Science (PDF), 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 (PDF), 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