Hamiltonizität von k-regulären Graphen

24

Es ist bekannt, dass es NP-vollständig ist, um zu testen, ob ein Hamilton-Zyklus in einem 3-regulären Graphen existiert, auch wenn es planar (Garey, Johnson und Tarjan, SIAM J. Comput. 1976) oder bipartit (Akiyama, Nishizeki, und Saito, J. Inform. Proc. 1980) oder um zu testen, ob ein Hamilton-Zyklus in einem 4-regulären Graphen existiert, selbst wenn es sich um den Graphen handelt, der durch eine Anordnung von Jordan-Kurven gebildet wird (Iwamoto und Toussaint, IPL 1994).

Für welches andere k ist es bekannt, dass es NP-vollständig ist, um die Hamiltonizität von k-regulären Graphen zu testen?

Der spezielle Fall, an dem ich interessiert bin, sind 6-reguläre Diagramme, mit der zusätzlichen Bedingung, dass das Diagramm eine ungerade Anzahl von Eckpunkten hat. Wenn gezeigt werden könnte, dass dieser Fall NP-vollständig (oder polynomisch) ist, hätte dies Auswirkungen auf ein Diagrammzeichnungsproblem, das unter http://arxiv.org/abs/1009.0579 beschrieben wird . Die Bedingung "ungerade Anzahl von Eckpunkten" ist, dass ich bei 6-regulären Diagrammen wirklich wissen möchte, ob der Graph entweder einen Hamilton-Zyklus oder einen zweigeteilten 2-Faktor enthält; Bei einer ungeraden Anzahl von Scheitelpunkten ist es jedoch unwahrscheinlich, dass ein zweiteiliger Faktor nur die Möglichkeit eines Hamilton-Zyklus lässt.

David Eppstein
quelle

Antworten:

15

Angenommen, der Graph hat eine gerade Anzahl von Eckpunkten. In der zweiten Stufe werden wir die Konstruktion erweitern, so dass wir, wenn k gerade ist, zeigen werden, wie man den Graphen in eine ungerade Anzahl von Scheitelpunkten verwandelt.

Die Lösung ist eine Verfeinerung der in der anderen Antwort vorgeschlagenen Idee.

Erster Teil

Behauptung: Wenn ein k regelmäßiger Graph G mit einer geraden Anzahl von Eckpunkten gegeben ist, kann man einen Graphen berechnen, Hder (k+1) -regelmäßig ist, und H ist ein Hamiltonscher iff G Hamiltonian ist.

Beweis: Man nehme zwei Kopien des regulären Graphen G und bezeichne sie als G 1 und G 2 . Für einen Eckpunkt v V ( G ) seien v 1 und v 2 die entsprechenden Kopien. Erstellen Sie eine Clique mit k + 2 Eckpunkten für v . Pick zwei Eckpunkte v ' und V " in dieser Clique, und entfernt den Rand zwischen ihnen. Als nächstes verbinde v 1 mit v ' und v 2kGG1G2vV(G)v1v2k+2vvvv1vv2zu . Sei C ( v ) diese Komponente für v .vC(v)v

Wiederholen Sie dies für alle Eckpunkte von und lassen Sie H den resultierenden Graphen bezeichnen.GH

Der Graph ist eindeutig k + 1 regulär. Wir behaupten, dass H genau dann Hamilton ist, wenn G Hamilton ist.Hk+1HG

Eine Richtung ist klar. Bei einem Hambiltonschen Zyklus in können wir ihn in einen Zyklus in H übersetzen . Tatsächlich interpretieren wir einen Zyklus, der einen Scheitelpunkt v besucht , so, dass er sich von v 1 nach v 2 (oder umgekehrt) bewegt, während alle Scheitelpunkte in C ( v ) besucht werden . Als solches Dies resultiert in einem Hamilton - Operator - Zyklus in H . (Beachten Sie, dass wir hier die Tatsache verwenden, dass die ursprüngliche Anzahl der Eckpunkte gerade ist - wenn der Zyklus ungerade ist, bricht dies zusammen.)GHvv1v2C(v)H

Was die andere Richtung, hält einen Hamiltonschen Kreis in . Es muss sein, dass C ( v ) von einem Teil des Zyklus besucht wird, der in v 1 beginnt , alle Eckpunkte von C ( v ) besucht und von v 2 (oder der symmetrischen Option) abreist. Tatsächlich kann der Hamilton-Zyklus nicht von demselben v i aus betreten und verlassen werden . Als solches kann ein Hamilton - Operator - Zyklus in H als natürliche Interpretation als Hamilton - Operator Zyklus in G . QED.HC(v)v1C(v)v2viHG

Zweiter Teil

Wie unten von Tsuyoshi bemerkt, hat jedes 3-reguläre Diagramm eine gerade Anzahl von Eckpunkten. Aus diesem Grund ist das Problem für ein regelmäßiges Diagramm mit einer geraden Anzahl von Scheitelpunkten schwierig . Die obige Reduktion zeigt nämlich, dass das Problem für jedes k- reguläre Diagramm schwierig ist , obwohl das resultierende Diagramm eine gerade Anzahl von Eckpunkten aufweist.3k

Wir beobachten, dass dies impliziert, dass das folgende Problem NP-schwer ist.

Aufgabe A: Entscheiden, ob ein k-regulärer Graph mit einer geraden Anzahl von Eckpunkten einen Hamilton-Zyklus hat, der durch eine bestimmte Kante e verläuft .Ge

Wenn jedoch gerade dann eine Instanz ( G , e ) erhält , können wir es auf das gewünschte Problem reduzieren. In der Tat ersetzen wir die Kante e durch eine Clique von k + 1 Eckpunkten, bevor wir eine Kante in der Clique löschen und ihre beiden Endpunkte mit den Endpunkten von e verbinden und e aus dem Diagramm entfernen . Für den neuen Graphen H gilt :k(G,e)ek+1eeH

  • ist k- regulär.Hk
  • ist Hamiltonian, wenn G Hamiltonian mit einem Zyklus unter Verwendung von e ist .HGe
  • hat | V ( G ) | + k + 1 Eckpunkte => H hat eine ungerade Anzahl von Eckpunkten.H|V(G)|+k+1H

Beachten Sie, dass ein regelmäßiger Graph für k ungerade eine gerade Anzahl von Scheitelpunkten haben muss (zählen Sie nur die Kanten). Daher gibt es keine k- regelmäßigen Graphen mit ungerader Anzahl von Scheitelpunkten, wobei k ungerade ist.kkkk


Ergebnis

Es ist schwer zu entscheiden, ob ein regelmäßiger Graph einen Hamilton-Zyklus für k 3 hat . Das Problem bleibt NP-schwer, auch wenn der Graph eine ungerade Anzahl von Eckpunkten hat.kk3


Natürlich ist es immer möglich, dass ich einen dummen Fehler gemacht habe ...


Übung

Wenn wir von einem Diagramm, das regulär ist, zu einem Diagramm, das (sagen wir) 2 k- regulär ist, übergehen möchten, führt das Diagramm, das sich aus der Anwendung der obigen Reduktion ergibt, wiederholt zu einem Diagramm mit einer Größe, die exponentiell von k abhängt . Zeigen Sie, dass man mit einem k- regulären Graphen G und i > 2 einen Graphen H konstruieren kann , der ( k + i ) -regelmäßig ist und dessen Größe in k , i und n polynomisch ist , wobei n die Anzahl der Eckpunkte ist von Gk2kkkGi>2H(k+i)k,innG . Außerdem, ist genau dannHamiltonian,wenn H Hamiltonian ist.GH

(Ich poste dies als Übung, nicht als Frage, da ich weiß, wie ich das lösen kann.)

Sariel Har-Peled
quelle
1
Groß! Ich denke, dass diese Antwort tatsächlich die erste Frage „Für welches andere k ist es bekannt, dass es NP-vollständig ist, um die Hamiltonizität von k-regulären Graphen zu testen?“ Regelt, da die 3-regulären Graphen eine gerade Anzahl von Eckpunkten und den Graphen haben H, das durch diese Transformation erzeugt wurde, hat auch eine gerade Anzahl von Scheitelpunkten, wenn G eine gerade Anzahl von Scheitelpunkten hat.
Tsuyoshi Ito
Aber wenn ich mich nicht irre, ist das gleiche Gegenbeispiel zu Robins Beweis ein Gegenbeispiel zu diesem Beweis. Sei G der Pfad auf 2 Eckpunkten. Dann erzeugt die Prozedur hier H, was ein 9-Zyklus ist, was Hamilton ist.
Emil
Wie ich in Bezug auf Robins Antwort sagte, besteht das Problem darin, dass, wenn Sie versuchen, den Hamilton-Zyklus von H auf G zu "projizieren", der Zyklus möglicherweise kein Zyklus ist, weil er dort zurückverfolgt wird, wo er war.
Emil
@Emil: Ich denke, dass der Pfad auf 2 Eckpunkten wirklich ein Sonderfall ist, da er eine Hamilton-Schaltung hat, wenn wir dieselbe Kante mehr als einmal verwenden dürfen.
Tsuyoshi Ito
1
@Sariel Har-Peled: In jedem Diagramm ist die Anzahl der ungeraden Scheitelpunkte (dh der Scheitelpunkte ungeraden Grades) gerade. Daher haben alle 3-regulären Graphen eine gerade Anzahl von Eckpunkten. Ich hatte in der ersten Version des Kommentars (die ich in weniger als 5 Minuten geändert habe) ein unnötig kompliziertes Argument geschrieben, ohne es zu bemerken. Entschuldigen Sie mich, wenn Sie meinen alten Kommentar gelesen haben und verwirrt waren.
Tsuyoshi Ito
1

EDIT: Dieser Beweis ist falsch, wie in den Kommentaren ausgeführt. (Soll ich den Beitrag löschen?)

Es fühlt sich intuitiv so an, als ob Hamiltonicity für k-reguläre Graphen NP-hart ist, dann sollte es auch für (k + 1) -regelmäßige Graphen NP-hart sein. Hier ist eine Verkleinerung auf der Rückseite des Umschlags, die für mich gut aussieht, aber natürlich könnte es einen Fehler geben.

Sei G ein k-regulärer Graph. Sei G 'das graphische kartesische Produkt von G und eine Kante. Mit anderen Worten, G 'ist der Graph, der zwei Kopien von G hat, und jeder Scheitelpunkt ist mit seiner Kopie verbunden. G 'ist jetzt (k + 1) regulär, da jeder Eckpunkt 1 zusätzliche Kante hat.

Behauptung: G hat genau dann einen Hamilton-Zyklus, wenn G 'einen Hamilton-Zyklus hat.

Beweis: Wenn G einen Hamilton-Zyklus hat, ist es leicht zu erkennen, dass G 'auch einen hat. Sprich (u, v) ist eine Kante im Hamilton-Zyklus. Durchlaufen Sie den Zyklus von u nach v, ohne diese Kante zu verwenden, und gehen Sie jetzt statt der Kante zu v 'von v, wobei v' der Scheitelpunkt ist, der v in der Kopie von G entspricht. Durchlaufen Sie den Zyklus nun in umgekehrter Reihenfolge in dieser Grafik, die uns zurück zu u 'bringen wird. Gehen Sie nun von u 'zu u, um den Zyklus abzuschließen.

Wenn G 'einen Hamilton-Zyklus hat, der mit dem Scheitelpunkt u beginnt, betrachte die gleiche Folge von Durchläufen auf G. Jedes Mal, wenn eine Bewegung zu einem benachbarten Scheitelpunkt in demselben Graphen ausgeführt wird, wird dieselbe Bewegung in G ausgeführt. Jedes Mal, wenn eine Bewegung ausgeführt wird Für den entsprechenden Scheitelpunkt in der anderen Grafik tun wir nichts. Da jede Bewegung auf dem Graphen G gültig ist und der Zyklus auf dem Eckpunkt u endet, ist dies ein Hamilton-Zyklus.

Robin Kothari
quelle
1
Ich kann nicht sehen, wie der zweite Absatz des Beweises funktioniert. Wenn wir die Bedingung fallen lassen, dass G k-regulär ist, gibt die Angabe, dass G 'Hamilton ist, ein Gegenbeispiel für die Behauptung, dass G auch Hamilton ist.
Tsuyoshi Ito
1
Ich mache mir ein bisschen Sorgen um den letzten Absatz hier. Wenn der Hamilton-Zyklus für G 'auf G "projiziert" wird (wenn das das richtige Wort ist!), Kann es vorkommen, dass der Zyklus seine Schritte zurückverfolgt.
Emil
@ Tsuyoshi: Sie haben ein Gegenbeispiel: Nehmen Sie einfach einen regulären Pfad - den Pfad mit zwei Eckpunkten.
Emil
@ Tsuyoshi: Du hast recht. Der Beweis ist falsch. Soll ich die Antwort löschen? Haben wir eine Richtlinie dazu?
Robin Kothari
@Robin, ich denke, dein Beitrag sollte jetzt hinterlassen werden, da er einige Diskussionen ausgelöst hat. Dies zeigt deutlich, dass dies ein heikles Problem ist.
Emil