Ich möchte ein einfaches Gadget, um zu beweisen, dass der planare Hamilton-Zyklus NP-vollständig ist (aus dem Hamilton-Zyklus)

Es ist bekannt, dass der Hamilton-Zyklus (kurz Schinken) NP-vollständig und der planare Schinken-Zyklus NP-vollständig ist. Der Beweis für den Planaren Schinkenzyklus stammt nicht aus dem Schinkenzyklus.

Gibt es ein nettes Gadget, das bei einem gegebenen Graphen G alle Kreuzungen durch ein planares Gadget ersetzt, so dass Sie einen planaren Graphen G 'haben, so dass

G hat einen Ham-Zyklus, wenn G 'einen Ham-Zyklus hat.

(Ich freue mich über Varianten wie Ham Path oder Directed Ham Cycle oder Directed Ham Path.)

cc.complexity-theory np-hardness planar-graphs hamiltonian-paths Bill GASARCH
quelle

Eine etwas triviale Beobachtung. Angenommen, Sie betten und die Kanten und kreuzen sich, wobei im Uhrzeigersinn um den Kreuzungspunkt angezeigt werden. Ersetzen Sie es durch ein Gadget mit vier Eintrittspunkten , die . Wenn ein Hamilton-Zyklus in beide Kanten und müsste sich der entsprechende Zyklus in selbst kreuzen. Dies setzt natürlich die naivste Interpretation dessen voraus, was ein "Gadget" ist, und auch, dass der Hamilton-Zyklus in

G

$G$

(x, y)

$(x,y)$

(u, v)

$(u,v)$

x, v, y, u

$x,v,y,u$

P_{x v y u}

$P_{xvyu}$

x^{'}, v^{'}, y^{'}, u^{'}

$x',v',y',u'$

x, v, y, u

$x,v,y,u$

G

$G$

(x, y)

$(x,y)$

(u, v)

$(u,v)$

G^{'}

$G'$

G^{'}

$G'$ benötigt , um die gleichen wie die Kanten in entsprechenden Zyklus folgt .

G

$G$

Marek Chrobak

Was ist Schinkenzyklus? Bitte gehen Sie nicht davon aus, dass alle Ihre Abkürzungen verstehen.

Tsuyoshi Ito

@ MarekChrobak: Ich stimme Ihrer Bemerkung zu. Sie geben zwei Möglichkeiten, um sich Ihrer Auseinandersetzung zu entziehen. Ich denke, das natürlichste ist das zweite: Es gibt einen Hamilton-Zyklus in wenn es einen Hamilton-Zyklus .

x \to y \to \dots \to u \to v \to \dots \to x

$x\to y\to\dotsb\to u\to v\to\dotsb\to x$

G

$G$

x \to x^{'} \to \dots \to u^{'} \to u \to \dots \to y \to y^{'} \to \dots \to v^{'} \to v \to \dots \to x

$x\to x'\to\dotsb \to u'\to u\to\dotsb\to y\to y'\to\dotsb\to v'\to v\to\dotsb\to x$

Bruno

@ Tsuyoshi: Es bedeutet Hamilton-Zyklus. Ich denke, es ist vernünftig anzunehmen, dass jeder es herausfinden kann.

Domotorp

@Bill: Ich frage mich, warum du denkst, dass so ein Gadget existieren sollte. Die Anzahl der Übergänge beim Einbetten eines beliebigen Graphen in die Ebene kann sehr groß sein ( für den vollständigen Graphen - siehe das Kreuzungs-Lemma). Wenn Sie also mit einem Graphen mit Kanten und vielen Kanten (etwa quadratisch) beginnen, hat der eingebettete Graph mit den als Eckpunkte hinzugefügten Kreuzungen eine völlig andere Struktur ...

Θ (n^{4})

$\Theta(n^4)$

n

$n$

Sariel Har-Peled

Antworten:

Zumindest kein "nettes" Gerät für eine Frequenzweiche.

Sei und ein Kreuz, das wir ersetzen wollen. $(a, b)$ $(x,y)$ Bildbeschreibung hier eingeben

Es gibt viele Fälle für unser Diagramm, , aber wir müssen mindestens die folgenden vier erfüllen. Fall 1: Es gibt mindestens einen Hamilton-Zyklus, aber keiner verwendet eine der Kanten. Fall 2: Es gibt mindestens einen Zyklus, und alle Zyklen verwenden genau eine der beiden Flanken. Fall 3: Es gibt mindestens einen Zyklus, und alle Zyklen verwenden beide Flanken. Fall 4: Es gibt keinen Hamilton-Zyklus. $G$

Wenn unser Gadget zwei (oder mehr) Eckpunkte für jeden der , um alle benachbarten die gleichen Nachbarn (so dass und behalten ‚s Nachbarn) dann nicht notwendigerweise noch eben sein. Um den ersten unserer obigen Fälle zu erfüllen, können wir dann keine neuen Eckpunkte im Gadget haben. $a, b, x, y$ $a_0$ $a_1$ $a$ $G'$

Um den obigen Fall 3 zu erfüllen, müssen mindestens zwei Kanten im Gadget vorhanden sein. Weder das planare und das abdeckende Paar noch erfüllen den Fall 2, daher brauchen wir eine dritte Kante. Ohne Verlust der Allgemeinheit seien diese drei . $(a, x), (y, b)$ $(a, y), (x, b)$ $(a, y), (y, b), (x,b)$

Diese Ersetzung unterbricht jedoch den vierten Fall, da einen Hamilton-Zyklus enthalten könnte, wenn dies nicht tut. Nehmen wir zum Beispiel wobei und . ist nicht planar und hat keinen Hamilton-Zyklus. $G'$ $G$ $G = (V, E)$ $V = \{a, b, x, y, p, q, r, s, t\},$ $E = \{(a, b), (x, y), (a, r), (a, p), (a, q), (b, s), (b, x), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$ $G$ Bildbeschreibung hier eingeben

Dann ist wobei . ist planar und hat einen Hamilton-Zyklus ( ). $G' = (V, E')$ $E' = \{(a, y), (y, b), (x, b)\} \cup$ $\{(x, y), (a, r), (a, p), (a, q), (b, s), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$ $G'$ $a, q, x, t, p, s, b, y, r, a$

Es ist zu beachten, dass, wenn die Kante nicht anstelle von hinzugefügt worden wäre , keinen Hamilton-Zyklus haben würde. Es scheint jedoch, dass Sie den möglichen Zyklus kennen müssen, um die Kante richtig zu wählen. $(b, y)$ $(a, x)$ $G'$

Ein ähnliches Problem besteht darin, dass das Gadget eine der diagonalen Kanten enthält, wie z. : . $(a, b), (a, y), (x, b)$

Da das Hinzufügen von drei Kanten Fall 4 unterbricht, hilft das Hinzufügen von mehr nicht.

Somit existiert kein "nettes" Gadget. Es könnte sein, dass es ein Gerät gibt, das den Nachbarn von und mehr Aufmerksamkeit schenkt , aber das scheint nicht sehr "nett" zu sein. $a, b, x$ $y$

(Hinweis: Bitte lassen Sie mich wissen, wenn ich Fehler gemacht habe!)

( ~~Anmerkung 2: Ich hatte einige nette Figuren, kann sie aber nicht posten.~~ Gepostet.)

Kyle
quelle

Ich denke, Sie sollten jetzt in der Lage sein, Zahlen zu posten.

Jukka Suomela