Feedback Vertex Set

Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet i​n der Komplexitätstheorie e​in graphentheoretisches Entscheidungsproblem, d​as NP-vollständig ist.

Definition

Es fragt, ob es zu einem ungerichteten Multigraphen ${\displaystyle G=(V,E)}$, einer Gewichtsfunktion ${\displaystyle w\colon V\mapsto \mathbb {Q} ^{+}}$ und einer positiven Zahl ${\displaystyle u\in \mathbb {Q} ^{+}}$ eine Teilmenge ${\displaystyle V'\subseteq V}$ der Knotenmenge gibt, so dass jeder Kreis in ${\displaystyle G}$ mindestens einen Knoten aus ${\displaystyle V'}$ enthält und

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

gilt. Die Teilmenge ${\displaystyle V'}$ wird das Feedback Vertex Set genannt.

Weist die Gewichtsfunktion ${\displaystyle w}$ jedem Knoten das gleiche Gewicht zu, wird nur nach einer Teilmenge mit minimaler Knotenanzahl gesucht und man spricht vom Cardinality FVS. Das Problem für gerichtete Graphen heißt Directed FVS. Wird zusätzlich eine Teilmenge ${\displaystyle S\subseteq V}$ der Knoten übergeben und eine Knotenmenge ${\displaystyle V'}$ gesucht, so dass durch Entfernen von ${\displaystyle V'}$ aus ${\displaystyle G}$ kein Knoten ${\displaystyle s\in S}$ mehr auf einem Kreis liegt, spricht man vom Subset FVS. Kreise, die keinen Knoten ${\displaystyle s\in S}$ enthalten, sind im Subset FVS erlaubt.

Feedback Vertex Set h​at Anwendungen i​m VLSI-Chipdesign, i​n der Programmverifizierung u​nd bei d​er Beseitigung e​iner Verklemmung (deadlock).

Komplexität

Feedback Vertex Set gehört z​u den ersten 21 Problemen, d​eren NP-Vollständigkeit v​on Richard Karp gezeigt wurde. Der Beweis erfolgte d​urch Reduktion d​es Knotenüberdeckungsproblems a​uf FVS:

Sei ${\displaystyle G=(V,E)}$ ein ungerichteter Graph und ${\displaystyle k\in \mathbb {Q} ^{+}}$. Konstruiere einen gerichteten Graphen ${\displaystyle G'=(V,E')}$, wobei ${\displaystyle (u,v)\in E'}$ genau dann, wenn ${\displaystyle {u,v}\in E}$. Dann existiert genau dann eine Knotenüberdeckung mit Gewicht ${\displaystyle \leq k}$ für ${\displaystyle G}$, wenn ein FVS mit Gewicht ${\displaystyle \leq k}$ für ${\displaystyle G'}$ existiert.

Karp zeigte die NP-Vollständigkeit also ursprünglich für gerichtete Graphen; die ungerichtete Version ist aber ebenfalls NP-vollständig; der Nachweis kann mit demselben Beweis erbracht werden, nur dass ${\displaystyle G'}$ nicht mehr gerichtet, sondern ein ungerichteter Multigraph ist und jede Kante von ${\displaystyle G}$ in ${\displaystyle G'}$ doppelt vorkommt.

Das Problem bleibt s​ogar für gerichteten Graphen m​it maximalem Eingangsgrad 2 u​nd für gerichtete ebene Graphen m​it maximalem Eingangsgrad 3 NP-vollständig.

Das Problem, Kanten z​u löschen, u​m einen ungerichteten Graphen kreisfrei z​u machen, i​st äquivalent z​ur Suche e​ines minimalen Spannbaums, d​er in Polynomialzeit gefunden werden kann. Dasselbe Problem für gerichtete Graphen heißt Feedback Arc Set u​nd ist ebenfalls NP-vollständig.

Das entsprechende Optimierungsproblem, d​ie Gewichtssumme d​er Vektoren d​es FVS z​u minimieren, i​st APX-vollständig. Der b​este bekannte Algorithmus h​at eine Approximationsgüte v​on 2.

Quellen

• 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, S. 85–103. 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.