Feedback vertex set

From Wikipedia, the free encyclopedia

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.

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.

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

[edit] 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.
• 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.