imported>Phzh: Form, typo

2022-11-18T21:34:43Z

Form, typo

Neue Seite

Der Begriff '''Feedback Vertex Set''' bzw. '''kreiskritische Knotenmenge''' bezeichnet in der [[Komplexitätstheorie]] ein [[Graphentheorie|graphentheoretisches]] [[Entscheidungsproblem]], das [[NP-Vollständigkeit|NP-vollständig]] ist.

== Definition ==

Es fragt, ob es zu einem [[Ungerichteter Graph|ungerichteten]] [[Multigraph]]en <math>G = (V, E)</math>, einer Gewichtsfunktion <math>w\colon V \mapsto \mathbb{Q}^{+}</math> und einer positiven Zahl <math>u \in \mathbb{Q}^{+}</math> eine Teilmenge <math>V' \subseteq V</math> der Knotenmenge gibt, so dass jeder Kreis in <math>G</math> mindestens einen Knoten aus <math>V'</math> enthält und
:<math>\sum_{v \in V'} w(v) \leq u</math>
gilt. Die Teilmenge <math>V'</math> wird das Feedback Vertex Set genannt.

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

Feedback Vertex Set hat Anwendungen im [[VLSI]]-Chipdesign, in der [[Verifizierung#Informatik (Verifizieren von Software)|Programmverifizierung]] und bei der Beseitigung einer [[Verklemmung]] ''(deadlock)''.

== Komplexität ==

Feedback Vertex Set gehört zu den ersten [[Karps 21 NP-vollständige Probleme|21 Problemen]], deren NP-Vollständigkeit von [[Richard M. Karp|Richard Karp]] gezeigt wurde. Der Beweis erfolgte durch Reduktion des [[Knotenüberdeckungsproblem]]s auf FVS:

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

Karp zeigte die NP-Vollständigkeit also ursprünglich für [[Gerichteter Graph|gerichtete Graphen]]; die ungerichtete Version ist aber ebenfalls NP-vollständig; der Nachweis kann mit demselben Beweis erbracht werden, nur dass <math>G'</math> nicht mehr gerichtet, sondern ein ungerichteter [[Multigraph]] ist und jede Kante von <math>G</math> in <math>G'</math> doppelt vorkommt.

Das Problem bleibt sogar für gerichteten Graphen mit maximalem [[Eingangsgrad]] 2 und für gerichtete [[Ebener Graph|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 [[Minimaler Spannbaum|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 [[Approximationsalgorithmus#Klassen von Approximationsalgorithmen|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.
* {{Literatur
|Autor= [[Michael R. Garey]] und [[David S. Johnson]]
|Titel= [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
|Verlag=W.H. Freeman
|Datum=1979
|ISBN=0-7167-1045-5}} A1.1: GT7, S. 191.

{{Navigationsleiste Karps 21 NP-vollständige Probleme}}

[[Kategorie:Graphentheorie]]
[[Kategorie:Komplexitätstheorie]]

Feedback Vertex Set - Versionsgeschichte

imported>Phzh: Form, typo