Je veux un gadget facile à prouver Planar Hamiltonian Cycle NP-Complete (de Hamiltonian Cycle)

On sait que le cycle hamiltonien (jambon en abrégé) est NP-complet et que le cycle planaire du jambon est NP-complet. La preuve pour Planar Ham Cycle n'est pas de Ham Cycle.

Existe-t-il un joli gadget qui, étant donné un graphe G, remplacera tous les croisements par un gadget plan afin que vous ayez un graphe plan G 'tel que

G a un cycle de jambon ssi G 'a un cycle de jambon.

(Je serai heureux avec des variantes comme le chemin de jambon ou le cycle de jambon dirigé ou le chemin de jambon dirigé.)

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

Une observation quelque peu banale. Supposons que vous intégrez

G

$G$ et que les arêtes

(x, y)

$(x,y)$ et

(u, v)

$(u,v)$ croisent, avec

x, v, y, u

$x,v,y,u$ apparaissant dans le sens des aiguilles d'une montre autour du point de croisement. Remplacez-le par un gadget

P_{x v y u}

$P_{xvyu}$ qui a quatre points d'entrée

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

$x',v',y',u'$ correspondant à

x, v, y, u

$x,v,y,u$ . Si un cycle hamiltonien en

G

$G$ utilise les deux bords

(x, y)

$(x,y)$ et

(u, v)

$(u,v)$ alors en

G^{'}

$G'$ le cycle correspondant devrait s'auto-croiser. Ceci suppose bien entendu la plus naïve interprétation de ce qu'est un `` gadget » est et que le cycle hamiltonien dans

G^{'}

$G'$ doit suivre les mêmes bords que le cycle correspondant dans

G

$G$ .

Marek Chrobak

Qu'est-ce que le cycle du jambon? Veuillez ne pas supposer que tout le monde comprend vos abréviations.

Tsuyoshi Ito

@MarekChrobak: Je suis d'accord avec votre remarque. Vous donnez deux façons d'échapper à votre argument. Je pense que le plus naturel est le second: il y a un cycle hamiltonien

dans

ssi il existe un cycle hamiltonien

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: Cela signifie le cycle hamiltonien. Je pense qu'il est raisonnable de supposer que tout le monde peut le comprendre.

domotorp

@Bill: Je me demande pourquoi vous pensez qu'un tel gadget devrait exister. Le nombre de croisements lors de l'incorporation d'un graphe arbitraire dans le plan peut être très important (

pour le graphe complet - voir le lemme de croisement). Donc, si vous commencez avec un graphique avec

arêtes et de nombreuses arêtes (disons presque quadratiques), le graphique intégré avec les croisements ajoutés en tant que sommets a une structure complètement différente ...

Θ (n^{4})

$\Theta(n^4)$

n

$n$

Sariel Har-Peled

Réponses:

Non. Au moins, pas de gadget "sympa" pour un crossover.

Soit et une croix que nous voulons remplacer. $(a, b)$ $(x,y)$ enter image description here

Il existe de nombreux cas pour notre graphique, , mais nous devons satisfaire au moins les quatre suivants. Cas 1: il y a au moins un cycle hamiltonien, mais aucun n'utilise aucun des bords. Cas 2: il y a au moins un cycle et tous les cycles utilisent exactement l'un des deux bords. Cas 3: il y a au moins un cycle et tous les cycles utilisent les deux bords. Cas 4: il n'y a pas de cycle hamiltonien. $G$

Si notre gadget a deux (ou plus) des sommets pour chacun adjacent à tous les mêmes voisins ( de sorte que et conserver « voisins de l' époque) ne sera pas nécessairement toujours plan. Afin de satisfaire le premier de nos cas ci-dessus, nous ne pouvons alors pas avoir de nouveaux sommets dans le gadget. $a, b, x, y$ $a_0$ $a_1$ $a$ $G'$

Afin de satisfaire le cas 3 ci-dessus, nous devons avoir au moins deux bords dans le gadget. Ni les paires planes et couvrant, ni satisfont au cas 2, nous avons donc besoin d'une troisième arête. Sans perte de généralité, que ces trois soient . $(a, x), (y, b)$ $(a, y), (x, b)$ $(a, y), (y, b), (x,b)$

Cependant, ce remplacement casse le quatrième cas, car pourrait contenir un cycle hamiltonien quand ne le fait pas. Prenons, par exemple, où et $G'$ $G$ $G = (V, E)$ $V = \{a, b, x, y, p, q, r, s, t\},$ . n'est pas planaire et n'a pas de cycle hamiltonien. $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$ enter image description here

Alors où $G' = (V, E')$ $E' = \{(a, y), (y, b), (x, b)\} \cup$ . est planaire et a un cycle hamiltonien ( $\{(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$

Notez que si le bord n'était pas ajouté au lieu de , alors n'aurait pas de cycle hamiltonien. Il semble cependant qu'il faille connaître le cycle possible pour bien choisir l'arête. $(b, y)$ $(a, x)$ $G'$

Un problème similaire existe pour que le gadget inclue l'un des bords diagonaux, tels que: . $(a, b), (a, y), (x, b)$

Puisque l'ajout de trois bords rompt le cas 4, l'ajout de plus n'aidera pas.

$a, b, x$ $y$

(Remarque: faites-moi savoir si j'ai fait des erreurs ci-dessus!)

( ~~Remarque 2: j'ai eu de belles figures, mais je ne peux pas les poster.~~ Publié.)

Kyle
la source

I think you should be able to post figures now.

Jukka Suomela