Feedback Vertex Set

Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP-vollständig ist.

Definition

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

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

gilt. Die Teilmenge $V'$ wird das Feedback Vertex Set genannt.

Weist die Gewichtsfunktion $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 $S\subseteq V$ der Knoten übergeben und eine Knotenmenge $V'$ gesucht, so dass durch Entfernen von $V'$ aus $G$ kein Knoten $s\in S$ mehr auf einem Kreis liegt, spricht man vom Subset FVS. Kreise, die keinen Knoten $s\in S$ enthalten, sind im Subset FVS erlaubt.

Feedback Vertex Set hat Anwendungen im VLSI-Chipdesign, in der Programmverifizierung und bei der Beseitigung einer Verklemmung (deadlock).

Komplexität

Feedback Vertex Set gehört zu den ersten 21 Problemen, deren NP-Vollständigkeit von Richard Karp gezeigt wurde. Der Beweis erfolgte durch Reduktion des Knotenüberdeckungsproblems auf FVS:

Sei $G=(V,E)$ ein ungerichteter Graph und $k\in \mathbb {Q} ^{+}$. Konstruiere einen gerichteten Graphen $G'=(V,E')$, wobei $(u,v)\in E'$ genau dann, wenn ${u,v}\in E$. Dann existiert genau dann eine Knotenüberdeckung mit Gewicht $\leq k$ für $G$, wenn ein FVS mit Gewicht $\leq k$ für $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 $G'$ nicht mehr gerichtet, sondern ein ungerichteter Multigraph ist und jede Kante von $G$ in $G'$ doppelt vorkommt.

Das Problem bleibt sogar für gerichteten Graphen mit maximalem Eingangsgrad 2 und für gerichtete ebene Graphen mit maximalem Eingangsgrad 3 NP-vollständig.

Das Problem, Kanten zu löschen, um einen ungerichteten Graphen kreisfrei zu machen, ist äquivalent zur Suche eines minimalen Spannbaums, der in Polynomialzeit gefunden werden kann. Dasselbe Problem für gerichtete Graphen heißt Feedback Arc Set und ist ebenfalls NP-vollständig.

Das entsprechende Optimierungsproblem, die Gewichtssumme der Vektoren des FVS zu minimieren, ist APX-vollständig. Der beste bekannte Algorithmus hat eine Approximationsgüte von 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.

Karps 21 NP-vollständige Probleme

Erfüllbarkeitsproblem der Aussagenlogik | Cliquenproblem | Mengenpackungsproblem | Knotenüberdeckungsproblem | Mengenüberdeckungsproblem | Feedback Arc Set | Feedback Vertex Set | Hamiltonkreisproblem | Integer Linear Programming | 3-SAT | graph coloring problem | Covering by cliques | Problem der exakten Überdeckung | 3-dimensional matching | Steinerbaumproblem | Hitting set | Rucksackproblem | Job sequencing | Partitionsproblem | Maximaler Schnitt