Feedback vertex set 1860368 121882473 2007-04-11T06:32:45Z Jrsteenhuisen 4089567 In [[computational complexity theory]], the '''feedback vertex set''' problem is a [[graph theory|graph-theoretical]] [[NP-complete]] problem. It was among the [[Karp's 21 NP-complete problems|first problems shown to be NP-complete]]. The [[decision problem]] can be formalized as follows: :INSTANCE: An [[undirected graph]] <math>G = (V, E)</math> and a positive integer <math>k</math>. :QUESTION: Is there a subset <math>X \subseteq V</math> with <math>|X| \leq k</math> such that <math>G</math> with the vertices from <math>X</math> deleted is [[cycle (graph theory)|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 graph]]s. 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|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. == 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. * {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5}} A1.1: GT7, pg.191. [[Category:NP-complete problems]] [[Category:Graph theory]]