Hamiltonicité des graphes k-réguliers

24

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.

David Eppstein
la source

Réponses:

15

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.kGH(k+1)HG

kGG1G2vV(G)v1v2k+2vvv 1 v v 2 v C ( v ) vvv1vv2v. 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.HGH

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

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 ) HGHvv1v2C(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 GHC(v)v1C(v)v2viHG

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.k3k

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 .eGe

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 Hk(G,e)ek+1eeH

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

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 kkkkk


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 3kk3


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 Hk2kkkGi>2H(k+i)k,innGGH

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

Sariel Har-Peled
la source
1
Génial! Je pense que cette réponse règle en fait la première question «Pour quel autre k est-il connu pour être NP-complet pour tester l'hamiltonicité des graphes k-réguliers?» Parce que les graphes 3-réguliers ont un nombre pair de sommets, et le graphique H fait par cette transformation a également un nombre pair de sommets si G a un nombre pair de sommets.
Tsuyoshi Ito
Mais à moins que je ne me trompe, le même contre-exemple à la preuve de Robin est un contre-exemple à cette preuve. Soit G le chemin sur 2 sommets. Ensuite, la procédure ici crée H, qui est un cycle de 9, qui est hamiltonien.
Emil
Comme je l'ai dit à propos de la réponse de Robin, le problème est que lorsque vous essayez de «projeter» le cycle de Hamilton de H sur G, le cycle peut finir par ne pas être un cycle, car il revient où il a été.
Emil
@Emil: Je pense que le chemin sur 2 sommets est vraiment un cas particulier car il a un circuit hamiltonien si on nous permet d'utiliser le même bord plus d'une fois.
Tsuyoshi Ito du
1
@Sariel Har-Peled: Dans chaque graphique, le nombre de sommets impairs (c'est-à-dire les sommets de degrés impairs) est pair. Par conséquent, tous les graphiques à 3 niveaux réguliers ont un nombre pair de sommets. J'avais écrit un argument inutilement compliqué sans m'en rendre compte dans la première version du commentaire (que j'ai modifié en moins de 5 minutes), alors excusez-moi si vous lisez mon ancien commentaire et que vous en êtes confus.
Tsuyoshi Ito
1

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.

Robin Kothari
la source
1
Je ne vois pas comment fonctionne le deuxième paragraphe de la preuve. Si nous laissons tomber la condition que G est k-régulier, laisser G être un chemin donne un contre-exemple à une affirmation que si G ′ est hamiltonien alors G est également hamiltonien.
Tsuyoshi Ito du
1
Je suis un peu préoccupé par le dernier paragraphe ici. Lorsque le cycle de Hamilton pour G 'est "projeté" (si c'est le bon mot!) Sur G, nous pouvons avoir une situation où le cycle revient sur ses pas.
Emil
@Tsuyoshi: vous avez un contre-exemple: prenez simplement un chemin régulier - le chemin avec deux sommets.
Emil
@Tsuyoshi: Vous avez raison. La preuve est fausse. Dois-je supprimer la réponse? Avons-nous une politique à ce sujet?
Robin Kothari
@Robin, je pense que votre message devrait être laissé maintenant qu'il a généré une discussion. Cela illustre certainement qu'il s'agit d'un problème délicat.
Emil