Feedback Vertex Set

The term feedback vertex set or circle critical node set called in complexity theory a graph- theoretic decision problem is NP -complete.

Definition

It asks whether there is a subset of the node set to an undirected multigraph, a weight function and a positive number such that each circle contains at least one node from in and apply. The subset is called the feedback vertex set.

Assigns the weight function each node are of equal importance, to only search for a subset with minimal number of nodes and one speaks of the cardinality FVS. The problem for directed graphs is called Directed FVS. If additionally pass a subset of the nodes and wanted a set of nodes, so that no node is by removing on a circle, one speaks of the subset FVS. Circuits that do not contain nodes are permitted in the subset FVS.

Feedback Vertex Set has applications in VLSI chip design, in program verification and the eliminating of a deadlock ( deadlock ).

Complexity

Feedback Vertex Set is one of the first 21 problems whose NP- completeness has been shown by Richard Karp. The proof was by reduction of the vertex cover problem on FVS:

Be an undirected graph and. Construct a directed graph, if and only if. Then there exists iff a vertex cover with weight for when an FVS exists with weight.

Karp showed the NP- completeness that is originally for directed graphs; the undirected version, however, is also NP- complete; the proof can be provided with the same proof, except that not more directed, but an undirected multigraph and each edge appears twice in of.

The problem remains NP-complete even for directed graphs with maximum in-degree 2 and for directed planar graphs with maximum in-degree 3.

The problem, delete edges to make an undirected graph cycle-free, is equivalent to finding a minimum spanning tree, which can be found in polynomial time. The same problem for directed graphs is called Feedback Arc Set and is also NP -complete.

The corresponding optimization problem is to minimize the sum of the weight vectors of the BSS is the APX -complete. The best known algorithm has an approximation ratio of 2

Swell

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

Satisfiability of propositional logic | clique problem | Quantity packing problem | vertex cover problem | Quantity cover problem | Feedback Arc Set | Feedback Vertex Set | Hamilton cycle problem | Integer Linear Programming | 3-SAT | graph coloring problem | Covering by Cliques | problem of exact registration | 3 - dimensional matching | Steiner tree problem | Hitting set | knapsack problem | Job sequencing | partition Problem | Maximum average

• Graph Theory
• Complexity Theory