Feedback Vertex Set

In complexity theory , the term feedback vertex set or circle-critical node set denotes a graph-theoretical decision problem that is NP-complete .

definition

It asks whether there is a subset of the node set for an undirected multigraph , a weight function and a positive number such that each circle contains at least one node from and ${\ displaystyle G = (V, E)}$ ${\ displaystyle w \ colon V \ mapsto \ mathbb {Q} ^ {+}}$ ${\ displaystyle u \ in \ mathbb {Q} ^ {+}}$ ${\ displaystyle V '\ subseteq V}$ ${\ displaystyle G}$ ${\ displaystyle V '}$

{\ displaystyle \ sum _ {v \ in V '} w (v) \ leq u}

applies. The subset is called the feedback vertex set. ${\ displaystyle V '}$

If the weight function assigns the same weight to each node, only a subset with a minimal number of nodes is searched for and one speaks of Cardinality FVS . The problem for directed graphs is called Directed FVS . If a subset of the nodes is also transferred and a node set is searched for, so that by removing from there no more nodes are on a circle, one speaks of the subset FVS . Circles that do not contain a node are allowed in the FVS subset. ${\ displaystyle w}$ ${\ displaystyle S \ subseteq V}$ ${\ displaystyle V '}$ ${\ displaystyle V '}$ ${\ displaystyle G}$ ${\ displaystyle s \ in S}$ ${\ displaystyle s \ in S}$

Feedback vertex set has applications in VLSI -Chipdesign, in the program verification and in the elimination of a deadlock (deadlock) .

complexity

Feedback Vertex Set is one of the first 21 problems whose NP-completeness was shown by Richard Karp . The proof was carried out by reducing the node coverage problem to FVS:

Let be an undirected graph and . Construct a directed graph , where if and only if . Then there is a node coverage with weight for if and only if an FVS with weight for exists. ${\ displaystyle G = (V, E)}$ ${\ displaystyle k \ in \ mathbb {Q} ^ {+}}$ ${\ displaystyle G '= (V, E')}$ ${\ displaystyle (u, v) \ in E '}$ ${\ displaystyle {u, v} \ in E}$ ${\ displaystyle \ leq k}$ ${\ displaystyle G}$ ${\ displaystyle \ leq k}$ ${\ displaystyle G '}$

Karp thus originally showed NP-completeness for directed graphs ; the undirected version is also NP-complete; the proof can be provided with the same proof, only that it is no longer directed, but an undirected multigraph and every edge of in occurs twice. ${\ displaystyle G '}$ ${\ displaystyle G}$ ${\ displaystyle G '}$

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

The problem of deleting edges in order to make an undirected graph circular is equivalent to finding a minimal spanning tree that 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 to minimize the weight sum of the vectors of the FVS is APX-complete . The best known algorithm has a quality of approximation of 2.

swell

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