Gibt es einen effizienten Algorithmus für dieses Vertex-Cycle-Cover-Problem?

Ich habe versucht, einen Algorithmus zu finden, um eine maximale Scheitelpunktzyklusabdeckung eines gerichteten Graphen - dh eine Menge von disjunkten Zyklen, die alle Scheitelpunkte in , mit so vielen Zyklen wie möglich (wir berücksichtigen dies nicht) einzelne Eckpunkte zyklisch hier). Ich weiß, dass das Problem, eine minimale Vertex-Zyklus-Abdeckung sowie eine Vertex-Zyklus-Abdeckung mit genau Zyklen zu finden, NP-vollständig ist. Aber was ist mit dem Maximalfall?G $G$$G$$k$

Obwohl ich eine Antwort auf diese Frage im Allgemeinen interessant finde, sind die Graphen, für die ich sie verwenden möchte, durch ihre Konstruktion tatsächlich ziemlich eingeschränkt. Selbst wenn das Problem NP-vollständig ist, gibt es möglicherweise eine polynomielle Lösung für diese speziellen Fälle.

Wir haben eine Liste von Ganzzahlen , Elemente und wir werden , Elemente , um nach dem Sortieren auf zu verweisen . Als Beispiel:l i S s i$L$$l_i$$S$$s_i$$L$

Die Eckpunkte des Graphen werden mit Paaren identifiziert so dass und . Der Graph hat genau dann eine gerichtete Kante wenn . (Ein Zyklus in diesem Diagramm entspricht einer Reihe von Werten, die zyklisch so permutiert werden können, dass sie in ihrer sortierten Position enden.)l i = n s i ≠ n ( n , i ) → ( m , j ) s j = $(n, i)$$l_i = n$$s_i \neq n$$(n, i) \rightarrow (m, j)$$s_j = n$

Das obige Beispiel würde das folgende Diagramm ergeben (unter Verwendung von 1-basierten Indizes):

Eine Sache, die nicht funktioniert, ist der gierige Ansatz, den kleinsten Zyklus wiederholt zu entfernen (wie dieses Beispiel zeigt).

Beachten Sie, dass dieses Problem (wenn ich keine Fehler gemacht habe) der Frage entspricht, wie viele Tauschvorgänge Sie zum Sortieren einer bestimmten Liste benötigen . (Welches ist der Grund, warum dieses Problem in erster Linie untersucht wurde.)

$|C|-1$$|C|$$-1$.) Das heißt, das Gewicht hängt von der Größe des Zyklus ab und nicht von den jeweiligen Kanten, die er enthält. Aber vielleicht gibt dies jemandem eine andere Idee, wie das Problem verringert werden kann.

Es scheint auch, dass die Begrenzung der Größe der Zyklen das Problem APX-schwer für allgemeine Graphen macht. Dies bedeutet nicht zwangsläufig, dass dies auch für die Maximierung der Anzahl der Zyklen gilt, und auch nicht für die hier betrachteten spezifischen Diagramme, aber es scheint hinreichend eng miteinander verbunden zu sein, dass dies wichtig sein könnte.

Zusammenfassend lässt sich sagen, dass für die nach dem obigen Verfahren erstellten Graphen eine maximale Abdeckung des Scheitelpunkt-disjunkten Zyklus gefunden werden kann.

Abgesehen davon würde mich auch interessieren, ob die maximale Abdeckung des vertex-disjunkten Zyklus auch eine effiziente Lösung für beliebige Graphen bietet, die mindestens eine Zyklusabdeckung zulassen (die wahrscheinlich als Antwort auf die Hauptfrage herausfallen wird), oder ob Allein die Bestimmung der Anzahl der Zyklen in der maximalen Abdeckung (im Gegensatz zu den tatsächlichen Kanten in jeder) macht das Problem einfacher. Ich poste diese Fragen gerne als separate Fragen, wenn die Leute der Meinung sind, dass sie selbst umfassende Antworten verdienen.

$G$$k$$k=2$$k=3$ $k$$k$

$G$$G$$((3/5)-\epsilon)$$\epsilon > 0$

Zu Einzelheiten und Nachweisen der vorstehenden Ansprüche siehe [1].

[1] Bläser, Markus und Bodo Manthey. "Zwei Approximationsalgorithmen für 3-Zyklus-Cover." Approximationsalgorithmen zur kombinatorischen Optimierung. Springer Berlin Heidelberg, 2002. 40-50.