Feedback Vertex Set

aus Wikipedia, der freien Enzyklopädie

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 , einer Gewichtsfunktion und einer positiven Zahl eine Teilmenge der Knotenmenge gibt, so dass jeder Kreis in mindestens einen Knoten aus enthält und

gilt. Die Teilmenge wird das Feedback Vertex Set genannt.

Weist die Gewichtsfunktion 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 der Knoten übergeben und eine Knotenmenge gesucht, so dass durch Entfernen von aus kein Knoten mehr auf einem Kreis liegt, spricht man vom Subset FVS. Kreise, die keinen Knoten 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 ein ungerichteter Graph und . Konstruiere einen gerichteten Graphen , wobei genau dann, wenn . Dann existiert genau dann eine Knotenüberdeckung mit Gewicht für , wenn ein FVS mit Gewicht für 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 nicht mehr gerichtet, sondern ein ungerichteter Multigraph ist und jede Kante von in 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