Feedback Vertex Set

Input

Directed graph $G = (V, A)$, positive integer $K \leq |A|$.

Question

Is there a subset $V' \subseteq V$ with $|V'| \leq K$ such that $V'$ contains at least one vertex from every directed cycle in $G$?

Classes

• NP-complete

Comments

Remains NP-complete for digraphs having no in- or out- degree exceeding 2, for planar digraphs with no in- or out-degree exceeing 3 (Garey & Johnson, 1979), and for edge digraphs (Gavril, 1977), but can be solved in polynomial time for reducible graphs (Shamir, 1977). The corresponding problem for undirected graphs is also NP-complete.

Proofs

NP-complete

Transformation from Vertex Cover (Karp, 1972).

Reducible from

• Vertex Cover

References

• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.
• Gavril, F. (1977). “Some NP-complete problems on graphs”, Proc. 11th Conf. on Information Sciences and Systems, Johns Hopkins University, Baltimore, MD.
• Shamir, A. (1977). Finding Minimum Cutsets in Reducible Graphs [Techreport]. MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE.
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9