Feedback Vertex Set

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: 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.

Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Feedback vertex set — In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph.… …   Wikipedia

  • Feedback arc set — In graph theory, a directed graph may contain directed cycles, a one way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG). One way to do this is simply to… …   Wikipedia

  • Feedback (disambiguation) — Feedback is information about actions returned to the source of the actions. To request for feedback on new articles and major edits go .Feedback may also refer to: * Positive feedback, a feedback system that responds to perturbation in the same… …   Wikipedia

  • Hitting-Set-Problem — Das Hitting Set Problem ist ein NP vollständiges Problem aus der Mengentheorie. Es gehört zur Liste der 21 klassischen NP vollständigen Probleme von denen Richard M. Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte. Gegeben ist eine… …   Deutsch Wikipedia

  • Directed acyclic graph — An example of a directed acyclic graph In mathematics and computer science, a directed acyclic graph (DAG i …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Kreiskritische Knotenmenge — 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) …   Deutsch Wikipedia

  • Cycle graph — This article is about connected, 2 regular graphs. For other uses, see Cycle graph (disambiguation). Cycle graph A cycle graph of length 6 Vertices n …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”