Längster Zyklus in zwei Zyklen

Ist das folgende Problem NP-vollständig? (Ich nehme ja an).

Eingabe: ein ungerichteter Graph, bei dem der Kantensatz in zwei kantendisjunkte einfache Zyklen zerlegt werden kann (diese sind nicht Teil der Eingabe). $k \in \mathbb{N},G=(V,E)$

Frage: Gibt es in einen einfachen Zyklus mit einer Länge größer als ? $G$ $k$

Offensichtlich liegt das Problem in NP und der maximale Grad in ist , aber das scheint nicht zu helfen. $G$ $\leq 4$

graph-theory np-complete decision-problem Auflistung
quelle

Ich glaube nicht, dass Sie Recht haben mit "höchstens 4 Pfaden, die ein Paar verbinden". Siehe: i.imgur.com/mYL4n1V.png

svinja

@svinja Du hast recht, ich hätte sagen sollen, dass höchstens 4 paarweise kantendisjunkte Pfade zwischen einem Paar von zwei Eckpunkten existieren.

Listing

Ihr Titel ist irreführend, da der längste einfache Zyklus keiner der beiden Zyklen bei der Zerlegung von

(bei jeder Zerlegung).

E

$E$

Denis

@dkuper es kann tatsächlich die Vereinigung von zwei vertex disjunkten einfachen Zyklen betrachten.

Listing

Mein Punkt ist nicht, dass es niemals einer von ihnen sein kann, es ist, dass es manchmal nicht einer von ihnen ist. Das Problem ist also nicht, den größeren von beiden zu finden.

Denis

Antworten:

Ein Reduktionsversuch ....

Reduktion vom Hamilton-Pfad auf Digraph mit maximalem Grad 3, der NPC ist [G & J] $G = (V,E)$

Ignorieren Sie die Richtung der Kanten und teilen Sie die Kanten von mithilfe eines ersten (ungerichteten) Tiefenscans von einem beliebigen Knoten in zwei Sätze unterschiedlicher (ungerichteter) Pfade (in den Abbildungen rot und grün). $G$
Verbinden Sie die roten Pfade und fügen Sie zusätzliche "Verbindungsknoten" hinzu (violette Knoten in Abbildung B), und erstellen Sie eine ungerichtete rote Schaltung. Verbinden Sie die grünen Pfade und fügen Sie zusätzliche "Verbindungsknoten" hinzu (lila Knoten in der Abbildung), und erstellen Sie eine ungerichtete grüne Schaltung.
transformieren Sie jeden ursprünglichen Knoten von Grad 1 und Grad 2 (Abbildung C), indem Sie gelbe Knoten am eingehenden roten Rand und gelbe Knoten am ersten ausgehenden roten Rand hinzufügen ; Fügen Sie schließlich gelbe Knoten "in Richtung" der zweiten ausgehenden grünen Kante indem Sie einen "umwickelten" Pfad um , der die äußersten gelben Knoten der roten Kanten berührt (Abbildung D). $b \in V$ $k$ $a\to b$ $k$ $b \to c$ $k$ $b \to d$ $b$

In der resultierenden Grafik können alle gelben Knoten nur auf die beiden in Abbildung E und Abbildung F gezeigten Arten, die den beiden gültigen Durchquerungen des ursprünglichen Knotens entsprechen, durch einen einfachen Pfad durchlaufen werden . Informell, wenn eine Kante in Richtung des zusätzlichen "verknüpfenden" violetten Knotens verwendet wird, können gelbe Knoten nicht durchlaufen werden. $3k$ $b \in V$ $k$

transformiere jeden ursprünglichen Knoten von V von Grad 2 und Grad 1 auf ähnliche Weise

Wählen Sie ein ausreichend großes hat der Ergebnisgraph genau dann einen einfachen Pfad mit einer Länge von mehr als wenn der ursprüngliche Graph einen Hamilton-Pfad (mit der Länge ) hat $k \gg |V|$ $G'$ $3k(|V|-1)$ $G$ $|V|-1$

Geben Sie hier die Bildbeschreibung ein

Das größere Bild kann hier heruntergeladen werden

Vor
quelle

Dies ist ein sehr schöner Beweis. Vielleicht sollten Sie die Kanten in Abbildung 'A' richten, um leichter zu verstehen, wie man die Pfade erhält (ich glaube, ich habe es verstanden).

Listing

@Listing: Die Konstruktion der Pfade hängt nicht von den gerichteten Kanten ab (tatsächlich habe ich in der Antwort eine "ungerichtete" Suche geschrieben). Sie sollten von einem beliebigen Knoten aus starten, zuerst einen Tiefenscan durchführen, indem Sie die durchquerten Kanten mit Rot färben, dann zum ersten Knoten des Grades 3 zurückkehren und den ersten Tiefenscan mit Grün durchqueren, um die Kanten zu durchqueren, und so weiter. .. vielleicht hat es eine formalere Definition, aber es kommt mir jetzt nicht in den Sinn. Lassen Sie mich wissen, wenn Sie weitere Details benötigen.

Vor

Ich sehe, dass die Eigenschaft, dass Kanten in der 'richtigen' Richtung durchlaufen werden, durch die letzte Transformation erzwungen wird. Danke für die Abklärung.

Listing

Inspiriert von Vor's Antwort möchte ich eine einfachere geben.

Beginnen Sie mit dem Hamiltonschen Zyklusproblem für das Problem der Gittergraphen, das von Itai als schwierig erwiesen wurde.

Es ist leicht zu erkennen, dass die Kantenmenge eines Gittergraphen in zwei disjunkte Teilmengen unterteilt werden kann: horizontal und vertikal.

Jetzt müssen wir alle horizontalen in einen einfachen Zyklus und alle vertikalen in einen anderen einfachen Zyklus verweben.

Dies ist eine sehr einfache Aufgabe: Bei vertikalen Aufgaben von ganz links nach ganz rechts streichen, einfach alle vertikalen Lücken verbinden, dann eine aufeinanderfolgende x-koordinierte vertikale Linie verbinden und dann den niedrigsten Scheitelpunkt ganz links mit dem Scheitelpunkt ganz rechts verbinden. Ähnliches gilt für horizontale Kanten.

Beachten Sie, dass das erhaltene Diagramm immer noch einfach und ungerichtet ist und die Anforderungen erfüllt. Es ist einfach, weil wir uns in den letzten Schritten der vertikalen und horizontalen Phase mit zwei verschiedenen Scheitelpunktpaaren befassen.

$k$ $k$ $2k|V|$

Thinh D. Nguyen
quelle