Hamiltonizität von k-regulären Graphen

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.

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, $H$der $(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 $k$$G$$G_1$$G_2$$v \in V(G)$$v_1$$v_2$$k+2$$v$$v'$$v''$$v_1$$v'$$v_2$zu . Sei C ( v ) diese Komponente für v .$v''$$C(v)$$v$

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

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

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.)$G$$H$$v$$v_1$$v_2$$C(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.$H$$C(v)$$v_1$$C(v)$$v_2$$v_i$$H$$G$

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.$3$$k$

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 .$G$$e$

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)$$e$$k+1$$e$$e$$H$

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

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.$k$$k$$k$$k$

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.$k$$k\geq 3$

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 $k$$2k$$k$$k$$G$$i >2$$H$$(k+i)$$k,i$$n$$n$$G$ . Außerdem, ist genau dannHamiltonian,wenn H Hamiltonian ist.$G$$H$

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

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.