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

23

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é.)

Bill GASARCH
la source
7
Une observation quelque peu banale. Supposons que vous intégrez G et que les arêtes (x,y) et (u,v) croisent, avec x,v,y,u apparaissant dans le sens des aiguilles d'une montre autour du point de croisement. Remplacez-le par un gadget Pxvyu qui a quatre points d'entrée x,v,y,u correspondant à x,v,y,u . Si un cycle hamiltonien enG utilise les deux bords(x,y) et(u,v) alors enG 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 dansG doit suivre les mêmes bords que le cycle correspondant dansG .
Marek Chrobak
4
Qu'est-ce que le cycle du jambon? Veuillez ne pas supposer que tout le monde comprend vos abréviations.
Tsuyoshi Ito
2
@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 G ssi il existe un cycle hamiltonien x x u u y y v v x .xyuvxGxxuuyyvvx
Bruno
12
@Tsuyoshi: Cela signifie le cycle hamiltonien. Je pense qu'il est raisonnable de supposer que tout le monde peut le comprendre.
domotorp
3
@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 n 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 ...Θ(n4)n
Sariel Har-Peled

Réponses:

13

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

Soit et ( x , y ) 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 un 0 et un 1 conserver un « voisins de l' époque) G ' 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,ya0a1aG

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 ( a , y ) , ( x , b ) ne 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 , y ) , ( y , b ) , ( x , b ) .(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 G ne le fait pas. Prenons, par exemple, G = ( V , E )V = { a , b , x , y , p , q , r , s , t } , et E = { ( a , b ) , ( x , y )GGG=(V,E)V={a,b,x,y,p,q,r,s,t}, . G 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)}Genter image description here

Alors E = { ( a , y ) , ( y , b ) , ( x , b ) } { ( x , y ) , ( a , r ) , ( a , p ) , ( a , q ) , (G=(V,E)E={(a,y),(y,b),(x,b)} . G est planaire et a un cycle hamiltonien ( a , q , x , t , p , s , b{(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 ( a , x ) , alors G ' 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,xy

(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