Hamiltonicité des graphes k-réguliers

On sait qu'il est NP-complet de tester si un cycle hamiltonien existe dans un graphe à 3 réguliers, même s'il est planaire (Garey, Johnson et Tarjan, SIAM J.Comput.1976) ou bipartite (Akiyama, Nishizeki, et Saito, J. Inform. Proc. 1980) ou pour tester si un cycle hamiltonien existe dans un graphe à 4 régularités, même lorsqu'il s'agit du graphe formé par un arrangement de courbes de Jordan (Iwamoto et Toussaint, IPL 1994).

Pour quel autre k est-il connu pour être NP-complet pour tester l'hamiltonicité des graphes k-réguliers?

Le cas particulier qui m'intéresse est celui des graphes à 6 régularités, avec la condition supplémentaire que le graphe ait un nombre impair de sommets. Si ce cas pouvait être démontré comme NP-complet (ou polynomial), il aurait un impact dans un problème de dessin de graphique décrit dans http://arxiv.org/abs/1009.0579 . La condition "nombre impair de sommets" est parce que ce que je veux vraiment savoir, pour les graphes à 6 intervalles réguliers, c'est que le graphe contient soit un cycle hamiltonien, soit un bipartite à 2 facteurs; mais avoir un nombre impair de sommets élimine la possibilité d'un facteur bipartite 2 ne laissant que la possibilité d'un cycle hamiltonien.

Première étape, supposons que le graphique a un nombre pair de sommets. Dans la deuxième étape, nous étendrons la construction, de sorte que si k est pair, alors nous montrerons comment transformer le graphique en un nombre impair de sommets.

La solution est un raffinement de l'idée suggérée dans l'autre réponse.

Première partie

Affirmation : Étant donné un graphe régulier G avec un nombre pair de sommets, on peut calculer un graphe H qui est ( k + 1 ) -régulier, et H est hamiltonien si G est hamiltonien.$k$$G$$H$$(k+1)$$H$$G$

$k$$G$$G_1$$G_2$$v \in V(G)$$v_1$$v_2$$k+2$$v$$v'$v 1 v ′ v 2 v ″ C ( v ) $v''$$v_1$$v'$$v_2$$v''$. Supposons que désigne ce composant pour .$C(v)$$v$

Répétez cette opération pour tous les sommets de et laissez désigner le graphique résultant.$G$$H$

Clairement, le graphique est régulier. Nous affirmons que est hamiltonien si et seulement si est hamiltonien.k + 1 H $H$$k+1$$H$$G$

Une direction est claire. Étant donné un cycle Hambiltonian dans , on peut le traduire en un cycle . En effet, chaque fois que le cycle visite un sommet , nous l'interprétons comme se déplaçant de à (ou vice versa) tout en visitant tous les sommets de . En tant que tel, il en résulte un cycle hamiltonien . (Notez que c'est là que nous utilisons le fait que le nombre initial de sommets est pair - si le cycle est impair, cela se décompose.)H v v 1 v 2 C ( v ) $G$$H$$v$$v_1$$v_2$$C(v)$$H$

En ce qui concerne l'autre direction, envisager un cycle hamiltonien . Il faut que soit visité par une partie du cycle qui commence en , visite tous les sommets de et part de (ou l'option symétrique). En effet, le cycle hamiltonien ne peut pas entrer et sortir du même . En tant que tel, un cycle hamiltonien comme une interprétation naturelle comme un cycle hamiltonien dans . QED.C ( v ) v 1 C ( v ) v 2 v i H $H$$C(v)$$v_1$$C(v)$$v_2$$v_i$$H$$G$

Deuxième partie

Comme indiqué ci-dessous par Tsuyoshi, tout graphique à 3 intervalles réguliers a un nombre pair de sommets. En tant que tel, le problème est difficile pour un graphe régulier avec un nombre pair de sommets. À savoir, la réduction ci-dessus montre que le problème est difficile pour tout graphique régulier, bien que le graphique résultant ait un nombre pair de sommets.$3$$k$

Nous observons que cela implique que le problème suivant est NP-difficile.

Problème A: décider si un graphe k-régulier avec un nombre pair de sommets a un cycle hamiltonien passant par une arête spécifique .$G$$e$

Cependant, si reçoit même une instance nous pouvons la réduire au problème souhaité. En effet, nous remplaçons l'arête par une clique de sommets, comme avant de supprimer une arête de la clique, de relier ses deux extrémités aux extrémités de , et de retirer du graphe. En clair, pour le nouveau graphique :( G , e ) e k + 1 e e $k$$(G, e)$$e$$k+1$$e$$e$$H$

• $H$ est régulier.$k$
• G $H$ est hamiltonien ssi est hamiltonien avec un cycle utilisant .$G$$e$
• | V ( G ) | + k + 1 $H$ a sommets => a un nombre impair de sommets.$|V(G)| + k+1$$H$

Notez qu'un graphe régulier, pour impair, doit avoir un nombre pair de sommets (il suffit de compter les bords) .Par conséquent, il n'y a pas de -graphes réguliers avec un nombre impair de sommets, étant impair.k k $k$$k$$k$$k$

Résultat

Il est NP-difficile de décider si un graphe régulier a un cycle hamiltonien pour . Le problème reste NP-difficile même si le graphique a un nombre impair de sommets.k ≥ $k$$k\geq 3$

Bien sûr, il est toujours possible que j'ai fait une erreur stupide ...

Exercice

Si nous voulons passer d'un graphique régulier à un graphique qui est (disons) régulier, le graphique résultant de l'application répétée de la réduction ci-dessus donne un graphique dont la taille dépend exponentiellement de . Montrer que, étant donné un graphe régulier , et , on peut construire un graphe qui est -régulier et sa taille est polynomiale en et , où est le nombre de sommets de . De plus, est hamiltonien si et seulement si est hamiltonien.2 k k k G i > 2 H ( k + i ) k , i n n G G $k$$2k$$k$$k$$G$$i >2$$H$$(k+i)$$k,i$$n$$n$$G$$G$$H$

(Je poste cela comme un exercice, pas comme une question, car je sais comment résoudre ce problème.)

EDIT: Cette preuve est fausse, comme indiqué dans les commentaires. (Dois-je supprimer le message?)

Il semble intuitivement que si l'hamiltonicité est NP-difficile pour les graphes k-réguliers, elle devrait également être NP-difficile pour les graphes (k + 1) -réguliers. Voici une réduction de l'arrière de l'enveloppe, qui me semble bien, mais bien sûr, il pourrait y avoir une erreur.

Soit G un graphe k-régulier. Soit G 'un produit cartésien graphique de G et une arête. En d'autres termes, G 'est le graphe qui a deux copies de G, et chaque sommet est connecté à sa copie. G 'est maintenant (k + 1) régulier, car chaque sommet a 1 bord supplémentaire.

Affirmation: G a un cycle hamiltonien si et seulement si G 'a un cycle hamiltonien.

Preuve: si G a un cycle hamiltonien, il est facile de voir que G 'en a un aussi. Disons que (u, v) est un bord du cycle hamiltonien. Traversez le cycle de u à v sans utiliser ce bord, et maintenant au lieu d'utiliser le bord, allez à v 'de v, où v' est le sommet correspondant à v dans la copie de G. Maintenant, parcourez le cycle dans l'ordre inverse dans ce graphique, qui nous ramènera à u '. Passez maintenant de u 'à u, ce qui termine le cycle.

Si G 'a un cycle hamiltonien à partir du sommet u, considérons la même séquence de traversées sur G. Chaque fois qu'un déplacement est effectué vers un sommet adjacent dans le même graphique, nous effectuons le même déplacement dans G. Chaque fois qu'un déplacement est effectué au sommet correspondant dans l'autre graphique, nous ne faisons rien. Puisque chaque mouvement est valide sur le graphe G et que le cycle se termine sur le sommet u, il s'agit d'un cycle hamiltonien.