In der Graphentheorie ist ein Scheitelpunktzyklusschnitt oder eine Rückkopplungsscheitelpunktmenge eine Menge von Scheitelpunkten in einem Graphen , so dass das Entfernen dieser Knoten den Graphen azyklisch verlässt . Mit anderen Worten, es ist eine Menge von Knoten, die mit jedem Zyklus einen Schnittpunkt ungleich Null haben .
Das Problem des Zyklusschneiders von Eckpunkten ist ein algorithmisches Problem der kombinatorischen Optimierung , das darin besteht, einen Zyklusschneider von Eckpunkten minimaler Größe zu finden.
Bei einem gegebenen ungerichteten Graphen G = (V, E) , ein Zyklus Schneider C ist eine Teilmenge von V , so dass die Graph G auf eingeschränkte V von entzogen C acyclisch ist , das heißt eine Gesamtstruktur .
Wir können jedem Scheitelpunkt s von G ein Gewicht w (s) zuordnen . Wir können auch einen gerichteten Graphen betrachten , dann geht es darum, alle gerichteten Zyklen zu schneiden.
Der Satz von Erdos und Posa besagt, dass es eine Funktion f gibt , so dass für jede ganze Zahl k jeder Graph einen k- disjunkten Zyklus (Eckpunkte) oder eine Größe der Eckpunktmenge f (k) hat . Darüber hinaus ist f (k) = O (k log k) .
Für jede ganze Zahl k ist die Familie von Graphen, deren minimaler Zyklusschnitt durch k begrenzt ist, eine Familie, die durch Moll geschlossen ist.
Das algorithmische Problem für den ungerichteten Fall und ohne Gewicht ist das folgende:
Die orientierten und gewichteten Fälle lassen sich leicht ableiten.
Das Problem in seiner Entscheidungsversion ist NP-vollständig und eines von Karps 21 NP-vollständigen Problemen .
Für das ungerichtete Problem gibt es einen Näherungsalgorithmus für das Verhältnis 2 mit Gewicht. Das Problem ist APX-vollständig, indem es auf das Problem der Scheitelpunktabdeckung reduziert wird .