Feedback vertex set

In computational complexity theory, the feedback vertex set problem is a graph-theoretical NP-complete problem. It was among the first problems shown to be NP-complete. The decision problem can be formalized as follows:

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

QUESTION: Is there a subset with such that G with the vertices from X deleted is cycle-free?

Karp originally showed the problem NP-complete on directed graphs, but the undirected version is also NP-complete. The problem remains NP-complete for directed graphs with no in-degree or out-degree exceeding 2, and also for planar directed graphs with no in-degree or out-degree exceeding 3. It can be solved in polynomial time for reducible graphs and undirected graphs of maximum vertex degree 3.

Note that the problem of deleting edges to make the graph cycle-free is equivalent to finding a minimum spanning tree, which can be done in polynomial time. On the other hand, the problem of deleting directed edges from a directed graph, called the feedback arc set problem, is also NP-complete.

The corresponding NP optimization problem of minimizing the number of vertices to delete is APX-complete. The best known approximation is by a factor of 2. It can be solved in time O(1.7548ⁿ), where n is the number of vertices in the graph. The number of minimal feedback vertex sets in a graph is O(1.8638ⁿ) (Fomin et al. 2008). The parameterized versions of the directed and undirected problems are fixed parameter tractable (Chen et al.).

The feedback vertex set problem has applications in genome assembly and VLSI chip design.

References

• Richard M. Karp. "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.. New York: Plenum, p.85-103. 1972. [1]
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A1.1: GT7, pg.191.

• 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 .
• Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5): (2008)
• Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, Yngve Villanger: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7): 1188-1198 (2008)