[4/6] Pourquoi les graphes hamiltoniens sont-ils difficiles ?

Précédemment dans « Cultivons-nous… Hamilton »

Une ville traversée par un fleuve. Sept ponts. Et une promenade impossible.

Dans le prologue de cette série, l’héritage d’Euler nous avait appris qu’un problème de parcours pouvait parfois être résolu sans essayer le moindre itinéraire. Pour savoir s’il était possible de traverser chaque pont exactement une fois, il suffisait de regarder les degrés des sommets. Quelques nombres pairs ou impairs, et le verdict tombait.

Puis un nouveau personnage est entré en scène. Dans Hamilton et le jeu icosien, les arêtes ont cédé la vedette aux sommets. Il ne s’agissait plus d’emprunter chaque passage, mais de visiter chaque lieu une seule fois avant de revenir au point de départ. Le décor semblait familier. Les règles, elles, venaient de changer.

Le deuxième épisode, Euler contre Hamilton, révélait alors le véritable piège. Euler permet souvent de diagnostiquer un graphe en examinant ses degrés. Hamilton oblige à construire un parcours dont tous les choix doivent rester compatibles jusqu’au dernier sommet. Un déplacement parfaitement autorisé peut préparer une impasse qui ne se révélera que beaucoup plus tard.

Dans le troisième épisode, deux théorèmes semblaient enfin offrir une issue. Lorsque le graphe est suffisamment bien connecté, Dirac ou Ore peuvent garantir qu’un cycle hamiltonien existe avant même que nous ayons commencé à le chercher. À l’inverse, certains obstacles structurels permettent parfois d’affirmer immédiatement qu’aucun cycle n’est possible.

Mais entre ces deux certitudes subsiste une immense zone grise.

Le cycle existe peut-être.
Peut-être pas.
Et cette fois, les théorèmes ne diront rien de plus.

La théorie a parlé. Puis elle s’est tue.

Il ne reste plus qu’un graphe, une multitude d’embranchements et une question inquiétante : combien de parcours faudra-t-il examiner avant de connaître la vérité ?

Du silence des théorèmes à la forêt des choix

Un théorème comme celui de Dirac ou d’Ore ressemble à un raccourci spectaculaire. On lui présente un graphe, on vérifie quelques conditions sur les degrés, et la conclusion tombe : un cycle hamiltonien existe. Nul besoin de le construire, encore moins d’examiner tous les parcours possibles.

Mais lorsque ces conditions ne sont pas satisfaites, il ne faut surtout pas conclure trop vite. Le théorème ne dit pas que le cycle n’existe pas. Il dit seulement qu’il ne peut pas nous le garantir.

C’est une nuance logique essentielle.

Ne pas disposer d’une preuve d’existence n’est pas disposer d’une preuve d’impossibilité.

Imaginons un graphe dans lequel aucun sommet n’est isolé, aucune coupure évidente ne condamne le parcours et où les degrés restent pourtant insuffisants pour appliquer Dirac ou Ore. Le dessin semble prometteur. Plusieurs chemins s’offrent immédiatement à nous. Certains paraissent même presque dessiner un cycle.

Alors nous choisissons un sommet de départ.

Deux voisins sont accessibles. Nous en sélectionnons un. Depuis ce nouveau sommet, trois directions deviennent possibles. Puis deux autres. À chaque étape, il faut avancer sans revisiter un sommet déjà utilisé, tout en conservant l’espoir de rejoindre finalement le point de départ.

Le problème ne vient pas de la difficulté de chaque décision prise isolément. Choisir un voisin parmi deux ou trois possibilités paraît anodin. Ce sont les conséquences cumulées de ces choix qui deviennent redoutables.

Une branche peut sembler parfaitement viable pendant longtemps. Le parcours visite presque tous les sommets, contourne plusieurs obstacles et paraît toucher au but. Puis, à quelques étapes de la fin, un sommet reste prisonnier à l’écart du cycle. Il n’est plus possible de l’insérer sans repasser par un sommet déjà visité.

Il faut alors revenir en arrière.

Pas seulement d’un sommet, parfois. Le mauvais choix peut avoir été effectué beaucoup plus tôt, à un embranchement qui paraissait sans importance. On défait donc le dernier déplacement, puis le précédent, jusqu’à retrouver une décision encore modifiable. On emprunte une autre branche et l’exploration recommence.

C’est le principe du retour sur trace, ou backtracking, déjà rencontré dans l’épisode précédent. Cette méthode permet d’éviter de poursuivre un chemin dès qu’il est manifestement condamné. Elle est plus intelligente qu’une énumération aveugle de tous les ordres possibles.

Mais elle n’est pas magique.

Dans certains graphes, les impasses apparaissent très vite : l’exploration élimine alors de nombreuses branches presque immédiatement. Dans d’autres, les mauvais parcours ne révèlent leur faiblesse qu’après avoir visité une grande partie des sommets. Le programme peut alors consacrer beaucoup de temps à explorer des pistes qui semblaient toutes raisonnables.

Le dessin initial se transforme peu à peu en un arbre invisible. Son tronc représente le sommet de départ. Chaque embranchement correspond à un choix possible. Chaque nouvelle décision fait naître d’autres branches, qui se divisent à leur tour. Certaines s’interrompent rapidement. D’autres s’enfoncent très loin avant de finir en impasse.

Et quelque part, peut-être, une branche referme enfin le cycle.

La difficulté du problème hamiltonien se cache dans cette forêt des choix. Elle ne saute pas toujours aux yeux sur le dessin. Deux graphes presque semblables peuvent demander des efforts de recherche très différents. Une seule arête ajoutée ou retirée peut ouvrir un raccourci décisif, condamner une famille entière de parcours ou repousser très loin le moment où une erreur devient visible.

Nous voilà donc face à une question plus précise. Ce n’est plus seulement :

Existe-t-il un cycle hamiltonien ?

Mais aussi :

Combien de choix faudra-t-il explorer pour le trouver — ou pour comprendre qu’il n’existe pas ?

Pour mesurer l’ampleur du problème, il suffit maintenant d’ajouter quelques sommets.

Quelques sommets de plus, des millions de parcours

Au premier regard, ajouter un sommet à un graphe paraît être une modification modeste. Un point supplémentaire, quelques arêtes nouvelles, rien qui semble devoir bouleverser le problème.

Pourtant, dans une recherche hamiltonienne, ce sommet ne vient pas simplement s’ajouter à la fin d’un parcours. Il peut prendre place avant le deuxième sommet, après le troisième, entre deux sommets déjà choisis… Chaque nouvelle position possible se combine avec toutes les organisations précédentes.

L’explosion…

Le nombre de parcours envisageables ne grandit donc pas régulièrement. Il explose.

Prenons le cas volontairement extrême d’un graphe complet à n sommets : chaque sommet y est relié à tous les autres. Une fois le sommet de départ fixé, tous les ordres de visite sont possibles. Il faut cependant éviter de compter plusieurs fois le même cycle : commencer la lecture à un autre endroit ne crée pas un nouveau cycle, et parcourir celui-ci dans le sens inverse ne change pas davantage son tracé.

Le nombre de cycles hamiltoniens distincts est alors donné par :

\dfrac{(n-1)!}{2}

Le point d’exclamation désigne ici une factorielle. Ainsi, la factorielle de 7 correspond au produit de tous les entiers de 1 à 7. Cette opération possède une redoutable particularité : sa croissance devient très rapidement vertigineuse.

Entre huit et dix sommets, le nombre de cycles est multiplié par 72. Avec seulement deux sommets supplémentaires, nous passons de quelques milliers de possibilités à près de deux cent mille.

• À douze sommets, il faut déjà compter près de vingt millions de cycles distincts.
• À quinze, plus de quarante-trois milliards.
• À vingt, le nombre dépasse soixante millions de milliards.

Travailler… pendant 2000 ans

Imaginons une machine capable d’examiner un million de parcours chaque seconde, sans jamais ralentir et sans commettre la moindre erreur. Pour parcourir la dernière ligne du tableau, elle devrait travailler pendant près de deux mille ans.

Le détective avait commencé son enquête avec quelques suspects. Il se retrouve désormais face à une foule plus nombreuse que tout ce qu’il pourrait interroger au cours d’une vie.

Dans les problèmes combinatoires, quelques éléments supplémentaires peuvent transformer une recherche raisonnable en exploration démesurée.

Il faut toutefois interpréter ce tableau avec prudence. Un graphe complet n’est pas un exemple difficile pour trouver un cycle hamiltonien : puisque toutes les arêtes existent, presque n’importe quel ordre de visite convient. Le tableau ne mesure donc pas directement le travail nécessaire pour résoudre ce cas particulier.

Révelation

Il révèle autre chose : la taille de l’univers dans lequel une recherche naïve pourrait être contrainte de se déplacer. Dans un graphe quelconque, une grande partie de ces ordres est éliminée parce que certaines arêtes manquent. Mais il reste parfois un nombre immense de parcours partiels qui semblent possibles avant de conduire à une impasse.

Supposons par exemple qu’un programme ait déjà visité dix sommets. Plusieurs prolongements restent disponibles. Il en choisit un, puis un autre, et poursuit jusqu’à ce qu’un sommet devienne inaccessible. Il revient alors au choix précédent, essaie une autre branche, avance de nouveau… Chaque échec élimine une possibilité, mais il peut rester derrière lui des milliers, des millions ou des milliards d’alternatives encore inexplorées.

C’est ici que l’apparence du graphe peut devenir trompeuse. Un dessin comportant vingt sommets tient facilement sur une feuille. L’œil humain les embrasse tous en une seconde. Pourtant, les ordres dans lesquels ils peuvent être visités forment un espace gigantesque, impossible à représenter sur cette même feuille.

Le graphe visible reste petit.

L’arbre des choix, lui, devient colossal.

Cette croissance explique pourquoi une méthode qui fonctionne parfaitement sur dix sommets peut devenir inutilisable sur vingt-cinq ou trente sommets. Le programme n’est pas nécessairement mal écrit. L’ordinateur n’est pas nécessairement trop lent. C’est le nombre de possibilités qui change d’échelle.

Une question apparaît alors : faut-il réellement explorer toute cette forêt ?

Heureusement, non. Dès qu’une branche ne peut plus produire de cycle hamiltonien, il est inutile de la prolonger. Toute l’intelligence d’un algorithme consiste à reconnaître ces branches condamnées le plus tôt possible.

Le retour sur trace peut ainsi couper une partie de la forêt avant de s’y perdre.

Mais certaines impasses savent parfaitement se dissimuler.

Le retour sur trace : intelligent, mais pas magique

Face à la forêt des choix, une première stratégie consisterait à dresser la liste de tous les ordres possibles, puis à vérifier chacun d’eux. Cette méthode finirait par donner la bonne réponse, mais elle consacrerait une énergie considérable à examiner des parcours dont l’échec était parfois prévisible dès leurs premières étapes.

Le retour sur trace procède autrement.

Il construit le parcours progressivement. À chaque étape, il choisit un sommet voisin qui n’a pas encore été visité. Tant que le chemin peut être prolongé, il avance. Dès qu’une branche devient impossible, il abandonne cette piste, revient au dernier embranchement et tente une autre direction.

Dans l’épisode précédent, ce mécanisme nous avait permis de rechercher effectivement un cycle hamiltonien. Nous allons maintenant regarder non plus seulement la réponse obtenue, mais le travail accompli pour l’obtenir.

Il suffit pour cela d’ajouter quelques compteurs au programme :

• le nombre d’appels à la fonction de recherche ;
• le nombre de branches abandonnées ;
• le nombre de fois où l’algorithme revient sur une décision ;
• éventuellement, le temps nécessaire pour conclure.

Deux graphes de même taille peuvent alors produire des résultats très différents.

Quand la bonne branche se présente immédiatement

Dans un premier graphe, les voisins sont examinés dans un ordre particulièrement favorable. Le programme choisit un sommet, puis un autre, et construit presque directement un cycle hamiltonien. Quelques branches seulement sont ouvertes. Le résultat apparaît rapidement.

Vu de l’extérieur, la recherche semble facile.

Mais cette rapidité tient peut-être simplement à la chance : la première piste explorée était la bonne. Si l’ordre des voisins avait été différent, le programme aurait pu commencer par plusieurs parcours trompeurs avant de découvrir exactement le même cycle.

Trouver rapidement une solution ne signifie pas toujours que le problème était facile. Cela peut simplement signifier que nous avons regardé au bon endroit en premier.

Quand l’impossibilité se révèle tout de suite

Dans un deuxième graphe, un sommet possède trop peu de possibilités, une branche isole une partie du dessin ou un chemin se referme trop tôt sans avoir visité tous les sommets. L’algorithme reconnaît rapidement que certaines décisions ne pourront jamais aboutir.

Le retour sur trace joue alors pleinement son rôle. Au lieu de prolonger inutilement un parcours condamné, il coupe la branche dès que l’impasse devient visible.

Cette élimination précoce peut faire disparaître d’un seul coup un grand nombre de prolongements inutiles. Une décision locale permet parfois d’éviter toute une sous-forêt de recherches.

Quand les mauvaises pistes paraissent excellentes

Le troisième cas est beaucoup plus redoutable.

Le parcours avance sans difficulté. Presque chaque sommet offre une continuation. Aucun sommet n’est isolé. Aucun blocage immédiat n’apparaît. L’algorithme visite cinq sommets, puis dix, puis presque tous les sommets du graphe.

Il ne reste plus qu’un dernier sommet.

Mais celui-ci ne peut plus être atteint. Ou bien il peut être atteint, mais le dernier sommet visité ne permet pas de revenir au point de départ. Le parcours, pourtant prometteur depuis le début, échoue à quelques mètres de l’arrivée.

Le programme retire alors son dernier choix. Il tente une autre possibilité. Celle-ci échoue à son tour. Il revient encore plus loin, modifie une décision prise plusieurs étapes auparavant et recommence à explorer.

C’est dans ce type de graphe que le retour sur trace montre sa limite.

Il sait abandonner une branche condamnée, mais il ne peut le faire qu’au moment où cette condamnation devient détectable. Si le piège ne se referme qu’à la fin du parcours, une grande partie du travail a déjà été accomplie.

Une impasse découverte tôt coûte peu.
Une impasse découverte au dernier sommet peut coûter une exploration entière.

Le retour sur trace n’empêche donc pas l’explosion du nombre de possibilités. Il tente de la contenir. Son efficacité dépend de la forme du graphe, de l’ordre dans lequel les choix sont examinés et de la capacité du programme à repérer rapidement les situations sans issue.

Choisir d’abord les sommets les plus contraints

Une amélioration naturelle consiste à ne pas visiter les voisins dans un ordre quelconque. On peut donner la priorité aux sommets qui offrent le moins de possibilités.

L’idée ressemble à une stratégie souvent utilisée dans les grilles logiques : lorsqu’une case ne peut recevoir que deux valeurs, il est généralement plus utile de l’étudier qu’une case pour laquelle dix choix restent ouverts.

Dans un graphe, un sommet de faible degré est plus contraint qu’un sommet relié à presque tous les autres. Le visiter tôt peut donc provoquer deux effets favorables :

• soit il s’intègre correctement dans le parcours et une contrainte importante est immédiatement satisfaite ;
• soit il conduit rapidement à une impasse, ce qui permet d’abandonner la branche avant d’avoir exploré de nombreux prolongements.

Cette règle ne garantit pourtant pas que la première branche sera la bonne. Une heuristique ne fournit pas une preuve. Elle organise la recherche dans l’espoir de rencontrer plus tôt les choix décisifs.

D’autres tests peuvent encore renforcer l’algorithme. Avant de poursuivre une branche, on peut vérifier qu’aucun sommet restant ne devient inaccessible, que le graphe encore disponible ne se sépare pas en plusieurs morceaux ou qu’aucun petit cycle ne se referme prématurément en laissant des sommets à l’extérieur.

Chaque vérification supplémentaire agit comme un garde forestier : elle interdit l’accès aux chemins dont on sait déjà qu’ils ne mèneront nulle part.

Mais ces contrôles ont eux-mêmes un coût. Un programme trop prudent peut passer beaucoup de temps à vérifier chaque branche. Un programme trop naïf s’enfonce dans des pistes inutiles. La conception d’un bon algorithme consiste donc à trouver un équilibre entre le coût du contrôle et les économies qu’il permet.

Une efficacité impossible à juger sur un seul exemple

Il serait tentant de lancer le programme sur un graphe, d’obtenir une réponse presque instantanée et d’en conclure que le problème hamiltonien est finalement bien maîtrisé.

Ce serait oublier que le temps d’une recherche dépend fortement de l’exemple choisi.

Un graphe peut offrir un cycle très facile à découvrir. Un autre, de même taille, peut obliger l’algorithme à parcourir une grande partie de l’arbre des choix. Un troisième peut ne contenir aucun cycle, tout en laissant croire longtemps que plusieurs parcours pourraient aboutir.

Pour évaluer réellement une méthode, il ne suffit donc pas de lui présenter un cas favorable. Il faut varier les graphes, leur densité, leur organisation et l’ordre dans lequel les sommets sont proposés.

On découvre alors une situation déroutante : certains grands graphes sont résolus presque immédiatement, tandis que des graphes plus petits résistent longtemps.

La difficulté ne dépend pas seulement du nombre de sommets.

Elle dépend aussi de la manière dont les choix sont organisés et dont les pièges sont dissimulés.

Le retour sur trace constitue ainsi une méthode indispensable. Sans lui, la recherche serait souvent aveugle. Grâce à lui, des millions de parcours peuvent parfois être écartés sans être examinés jusqu’au bout.

Mais aucun ordre judicieux, aucune coupure précoce et aucune heuristique simple ne garantit que tous les graphes seront résolus rapidement.

Pour comprendre pourquoi cette difficulté résiste aux meilleurs algorithmes connus, il faut maintenant distinguer deux tâches qui se ressemblent beaucoup moins qu’il n’y paraît : vérifier un cycle déjà proposé et découvrir ce cycle lorsqu’on ne sait pas où il se cache.

Vérifier vite n’est pas trouver vite

Un collègue affirme avoir découvert un cycle hamiltonien dans un graphe comportant plusieurs dizaines de sommets. Il nous transmet simplement la liste des sommets dans l’ordre où ils doivent être parcourus.

Pour contrôler sa proposition, le travail est parfaitement accessible.

Il suffit de vérifier que chaque sommet apparaît une seule fois, que deux sommets successifs sont bien reliés par une arête et que le dernier rejoint le premier. En parcourant une fois la liste, nous pouvons confirmer que le cycle est valide ou repérer l’endroit précis où il échoue.

Le graphe peut être grand. La vérification reste méthodique.

Lorsqu’une solution nous est donnée, nous savons exactement quoi contrôler.

La situation change radicalement lorsqu’aucune liste ne nous est proposée.

Il faut alors choisir un premier sommet, sélectionner l’un de ses voisins, poursuivre sans répétition, anticiper le retour final et éviter que certains sommets ne restent enfermés hors du parcours. Chaque décision ouvre de nouvelles possibilités, et rien ne garantit que les premiers choix seront compatibles avec les derniers.

La différence ressemble à celle qui sépare un labyrinthe déjà parcouru d’un labyrinthe encore inconnu.

Lorsque quelqu’un trace sur le plan un chemin allant de l’entrée à la sortie, vérifier ce trajet demande seulement de suivre le trait et de constater qu’il ne traverse aucun mur. Trouver soi-même ce chemin peut exiger de s’engager dans de nombreux couloirs, de reconnaître les impasses et de revenir plusieurs fois en arrière.

Le cycle hamiltonien présente la même dissymétrie.

Contrôler une réponse et produire cette réponse ne sont pas deux opérations de même nature.

Une preuve courte pour une recherche immense

Dans le vocabulaire de l’informatique théorique, la liste ordonnée des sommets joue le rôle d’un certificat. Elle ne raconte pas tout le travail nécessaire pour découvrir le cycle. Elle fournit seulement une preuve concrète que celui-ci existe.

Ce certificat est court : il contient chaque sommet une fois. Sa vérification est également rapide : on contrôle successivement les arêtes annoncées.

Le contraste peut être spectaculaire. Un programme peut avoir exploré des millions de branches avant de découvrir un cycle, puis transmettre son résultat sous la forme de quelques lignes immédiatement vérifiables.

Le temps consacré à trouver la solution ne se lit pas dans la solution elle-même.

Imaginons un coffre protégé par un code à dix chiffres. Lorsqu’un code nous est proposé, une seule tentative suffit pour savoir s’il ouvre le coffre. Sans indication, il pourrait être nécessaire d’essayer une quantité considérable de combinaisons.

La vérification est instantanée. La recherche, elle, peut être démesurée.

Et lorsque le cycle n’existe pas ?

La situation devient encore plus délicate lorsque la réponse attendue est négative.

Pour prouver qu’un cycle hamiltonien existe, il suffit d’en montrer un. Un seul parcours valide met fin au débat.

Pour affirmer qu’aucun cycle n’existe, on ne peut pas se contenter de présenter quelques tentatives infructueuses. Le fait que cent, mille ou un million de parcours aient échoué n’exclut pas qu’une solution se cache dans la branche suivante.

Une solution trouvée prouve immédiatement l’existence.
Une longue série d’échecs ne prouve pas encore l’impossibilité.

Certains graphes possèdent heureusement une obstruction facile à exhiber : un sommet de degré insuffisant, une coupure, un sous-ensemble dont la suppression crée trop de composantes ou une autre structure incompatible avec un cycle hamiltonien. Dans ces cas, une preuve théorique permet de conclure sans explorer tous les parcours.

Mais lorsque aucune obstruction simple n’apparaît, certifier l’absence de cycle peut obliger l’algorithme à éliminer un nombre immense de possibilités.

Il ne suffit plus de chercher jusqu’à trouver.

Il faut chercher jusqu’à être certain qu’il n’y a plus rien à trouver.

Deux familles de problèmes

Cette distinction conduit à deux grandes questions étudiées en informatique théorique.

La première consiste à se demander quels problèmes peuvent être résolus efficacement. Autrement dit, existe-t-il une méthode dont le temps de calcul reste raisonnable lorsque la taille des données augmente ?

Ces problèmes appartiennent à une famille traditionnellement appelée P.

La seconde question concerne les problèmes pour lesquels une solution proposée peut être vérifiée efficacement. On ne demande pas nécessairement de savoir comment cette solution a été obtenue. Il suffit de pouvoir la contrôler rapidement lorsqu’elle est fournie.

Cette famille est appelée NP.

Il faut ici se méfier d’une confusion fréquente :

NP ne signifie pas « non polynomial ».

Le sigle désigne historiquement les problèmes vérifiables en temps polynomial par une machine dite non déterministe. Pour suivre notre récit, il suffit de retenir une formulation plus intuitive : les problèmes de NP possèdent des solutions positives que l’on sait contrôler efficacement lorsqu’elles sont proposées.

Le problème du cycle hamiltonien entre parfaitement dans ce cadre. Une liste de sommets constitue un certificat simple, et sa validité se vérifie rapidement.

Mais savons-nous toujours trouver ce certificat rapidement ?

C’est précisément là que le mystère commence.

Tout ce que l’on sait résoudre vite se vérifie vite

Si nous disposons d’une méthode rapide pour résoudre un problème, nous pouvons naturellement vérifier rapidement sa réponse : il suffit, au besoin, de refaire le calcul.

Les problèmes de la famille P appartiennent donc également à la famille NP.

La question inverse est beaucoup plus profonde :

Tout problème dont une solution se vérifie rapidement peut-il également être résolu rapidement ?

Autrement dit, les familles P et NP sont-elles réellement différentes ?

À ce jour, personne ne connaît la réponse générale. Aucun algorithme polynomial n’a été découvert pour résoudre tous les cas du problème hamiltonien, mais personne n’a non plus démontré qu’un tel algorithme ne pouvait pas exister.

Nous savons construire des programmes efficaces sur de nombreux graphes. Nous savons exploiter des théorèmes, couper des branches, choisir de bonnes heuristiques et reconnaître certaines structures particulières.

Ce que nous ne savons pas faire, c’est garantir qu’une méthode restera rapide sur tous les graphes, quelle que soit la manière dont leurs pièges ont été organisés.

Le problème hamiltonien ne se contente donc pas de résister à quelques programmes maladroits. Il occupe une place centrale dans l’une des plus grandes énigmes des Mathématiques et de l’informatique.

Et sa difficulté ne s’arrête pas là.

Le cycle hamiltonien appartient à une catégorie de problèmes si importante qu’une méthode rapide pour le résoudre entraînerait, par un jeu de transformations, une méthode rapide pour une multitude d’autres problèmes.

Hamilton entre P, NP et NP-complet

Jusqu’ici, notre enquête semblait porter sur un problème bien particulier : trouver un cycle qui visite chaque sommet d’un graphe exactement une fois avant de revenir au point de départ.

Mais au début des années 1970, l’histoire prend une tout autre dimension.

Les chercheurs découvrent que le problème hamiltonien n’est pas un casse-tête isolé. Il appartient à une vaste famille de problèmes qui, derrière des apparences très différentes, semblent partager une même difficulté profonde.

Organisation d’un emploi du temps, satisfaction d’une formule logique, choix d’un ensemble de sommets, parcours d’un graphe, découpage d’objets ou tournée d’un voyageur : les décors changent, mais une mécanique commune apparaît.

Une solution proposée se vérifie rapidement. La découvrir semble parfois exiger une exploration gigantesque.

Une précision essentielle : le problème de décision

Lorsque les spécialistes classent le cycle hamiltonien parmi les problèmes NP-complets, ils considèrent d’abord une question très précise :

Ce graphe possède-t-il un cycle hamiltonien ?

La réponse attendue est simplement oui ou non.

Il ne s’agit pas encore de demander au programme d’afficher le cycle, de compter tous les cycles possibles ou de trouver le meilleur parcours selon une certaine mesure. Chacune de ces variantes constitue un problème distinct.

Cette formulation binaire peut sembler moins ambitieuse que la recherche effective d’un cycle. Pourtant, elle concentre déjà toute la difficulté essentielle. Si nous disposions d’une méthode rapide capable de répondre à cette question pour n’importe quel graphe, nous pourrions l’interroger plusieurs fois afin de reconstituer progressivement une solution lorsqu’elle existe.

Le véritable verrou se trouve donc déjà dans cette simple décision :

oui ou non ?

NP-difficile : quand tous les chemins mènent à Hamilton

Pour comprendre la suite, il faut introduire une idée particulièrement puissante : la réduction.

Réduire un problème à un autre ne signifie pas nécessairement le rendre plus petit ou plus facile. Cela signifie le transformer.

Imaginons que nous cherchions à résoudre un problème nommé A, mais que nous possédions une machine extraordinairement efficace pour résoudre un problème B. Une réduction consiste à convertir chaque instance de A en une instance de B, de manière que la réponse soit préservée.

Si la transformation est correctement construite, nous pouvons suivre trois étapes :

1. traduire le problème A dans le langage du problème B ;
2. utiliser notre machine pour résoudre B ;
3. interpréter sa réponse pour résoudre A.

La traduction doit elle-même rester rapide. Il serait inutile de gagner du temps sur la résolution si la transformation demandait déjà des siècles.

Dans le vocabulaire de la complexité, on exige donc une réduction réalisable en temps polynomial : le travail nécessaire augmente de manière contrôlée avec la taille du problème initial.

Un problème est déclaré NP-difficile lorsque tous les problèmes de NP peuvent être traduits vers lui par ce type de réduction.

Un problème NP-difficile est suffisamment expressif pour reproduire, sous une autre apparence, la difficulté de n’importe quel problème de NP.

Ce n’est plus seulement un problème parmi les autres.

Il devient une sorte de langage universel des difficultés combinatoires.

Transformer une formule logique en graphe

Prenons un problème qui ne ressemble, au départ, absolument pas à une promenade dans un graphe.

Une formule logique contient des variables pouvant prendre les valeurs vrai ou faux. La question consiste à déterminer s’il existe une attribution de ces valeurs qui rende toute la formule vraie. Ce problème porte le nom de satisfaisabilité, souvent abrégé en SAT.

Comment une formule logique pourrait-elle devenir un cycle hamiltonien ?

La réduction construit un graphe spécialement conçu pour représenter les choix logiques de la formule. Certains groupes de sommets obligent le cycle à choisir entre deux directions, correspondant par exemple aux valeurs vrai et faux. D’autres parties du graphe contrôlent que chaque clause de la formule est satisfaite.

Les détails de cette construction sont techniques, mais son principe est remarquable :

La formule possède une attribution satisfaisante si et seulement si le graphe construit possède un cycle hamiltonien.

Le graphe devient ainsi une mise en scène de la formule.

Les variables se transforment en embranchements. Les contraintes deviennent des passages obligés. Le cycle hamiltonien ne représente plus seulement un parcours : il encode une solution logique complète.

Si nous savions résoudre rapidement tous les problèmes de cycle hamiltonien, nous pourrions donc résoudre rapidement les formules logiques ainsi transformées.

Et le même principe s’étend à une multitude d’autres problèmes.

NP-complet : difficile à trouver, facile à vérifier

Le cycle hamiltonien possède maintenant deux propriétés.

D’une part, il appartient à NP : lorsqu’un cycle nous est proposé, nous pouvons vérifier rapidement qu’il traverse bien tous les sommets une seule fois et revient à son point de départ.

D’autre part, il est NP-difficile : tout problème de NP peut être transformé en un problème de cycle hamiltonien par une réduction adaptée.

La réunion de ces deux propriétés porte un nom :

Un problème est NP-complet lorsqu’il appartient à NP et qu’il est également NP-difficile.

Le mot complet indique que le problème concentre toute la difficulté de la famille NP, tout en restant lui-même à l’intérieur de cette famille.

Au début des années 1970, les travaux fondateurs de Stephen Cook et Leonid Levin ont établi le rôle central du problème SAT. Richard Karp a ensuite montré, grâce aux réductions polynomiales, qu’un grand nombre de problèmes combinatoires classiques partageaient cette même difficulté. Le circuit hamiltonien figure au cœur de cette histoire, la version non orientée ayant également été établie NP-complète durant cette période fondatrice.

Ce résultat change complètement notre regard sur le graphe posé devant nous.

Lorsque nous peinons à trouver un cycle hamiltonien, nous ne sommes pas simplement victimes d’un mauvais programme ou d’une heuristique mal choisie. Nous rencontrons l’un des représentants emblématiques d’une difficulté commune à des milliers de problèmes étudiés en Mathématiques et en informatique.

Le premier domino

Supposons maintenant qu’une chercheuse découvre demain un algorithme polynomial capable de décider si n’importe quel graphe possède un cycle hamiltonien.

La nouvelle dépasserait largement la théorie des graphes.

Puisque tous les problèmes de NP peuvent être réduits au cycle hamiltonien, nous pourrions procéder ainsi pour chacun d’eux :

1. transformer rapidement le problème initial en un graphe ;
2. appliquer le nouvel algorithme hamiltonien ;
3. traduire sa réponse dans le contexte de départ.

Un algorithme polynomial pour Hamilton entraînerait donc un algorithme polynomial pour tous les problèmes de NP.

Autrement dit :

Résoudre rapidement un seul problème NP-complet permettrait de résoudre rapidement tous les problèmes de NP.

Le premier domino ferait tomber tous les autres.

Comme les problèmes de P appartiennent déjà à NP, cela établirait alors l’égalité :

P = NP

À l’inverse, démontrer qu’aucun algorithme polynomial ne peut résoudre le cycle hamiltonien dans tous les cas suffirait à établir que :

P ≠ NP

Voilà pourquoi tant d’attention se porte sur les problèmes NP-complets. Chacun d’eux constitue une porte d’entrée possible vers la question générale.

Une énigme toujours ouverte

Malgré des décennies de recherches, personne ne sait aujourd’hui si P et NP sont égales ou différentes.

L’immense majorité des spécialistes pense que P est différente de NP. Cette conviction repose sur l’expérience accumulée, la résistance des problèmes NP-complets et l’échec de très nombreuses approches.

Mais une conviction, même largement partagée, n’est pas une démonstration.

Il pourrait exister un algorithme radicalement nouveau, encore invisible, capable de traverser la forêt des choix sans en explorer chaque branche. Ou bien cette forêt pourrait renfermer une difficulté fondamentale qu’aucun algorithme polynomial ne pourra contourner.

Nous ne savons pas laquelle de ces deux histoires est la bonne.

La question P contre NP fait ainsi partie des problèmes du millénaire sélectionnés par le Clay Mathematics Institute. Sa résolution est associée à un prix d’un million de dollars.

Mais l’enjeu dépasse très largement la récompense.

Une réponse modifierait notre compréhension des limites du calcul, de l’optimisation, de la démonstration automatique et de nombreux systèmes cryptographiques. Elle préciserait ce qu’une machine peut espérer découvrir efficacement — et ce qui pourrait rester inaccessible malgré toute sa puissance.

Ce que « NP-complet » ne signifie pas

Le terme peut donner l’impression qu’un verdict définitif vient d’être prononcé : le problème serait insoluble, impraticable ou nécessairement lent.

Ce serait aller beaucoup trop loin.

Dire que le cycle hamiltonien est NP-complet ne signifie pas que chaque graphe est difficile. Certains cycles apparaissent immédiatement. Certains graphes sont éliminés par un théorème. Certaines familles particulières disposent d’algorithmes efficaces.

Cela ne signifie pas davantage que tout programme devra nécessairement tester les parcours un par un. Les réductions, la programmation dynamique, les heuristiques, les méthodes algébriques et les techniques de séparation permettent de faire infiniment mieux qu’une exploration totalement naïve.

La NP-complétude porte sur le problème général et sur son comportement dans le pire des cas.

Elle ne condamne pas chaque instance.
Elle nous avertit qu’aucune méthode rapide valable pour toutes les instances n’est actuellement connue.

Un graphe à mille sommets peut parfois révéler facilement son cycle. Un autre, beaucoup plus petit, peut organiser ses contraintes de manière à déjouer longtemps nos meilleures stratégies.

La difficulté théorique n’interdit donc ni la recherche, ni les progrès, ni les solutions pratiques.

NP-complet ne signifie pas insoluble.

Il est temps de voir comment les mathématiciens et les informaticiens continuent malgré tout à attaquer ces problèmes, en exploitant la structure des graphes plutôt qu’en affrontant aveuglément toutes les possibilités.

Difficile ne signifie pas insoluble

Après l’explosion combinatoire, les retours sur trace interminables et la NP-complétude, le diagnostic pourrait sembler désespérant.

Faudrait-il renoncer dès que Dirac et Ore restent silencieux ? Abandonner tout graphe un peu grand sous prétexte que le pire cas menace ?

Heureusement, non.

La complexité décrit une difficulté générale.
Elle ne prédit pas le destin de chaque graphe particulier.

Un problème NP-complet peut être très facile sur certaines instances. Un cycle hamiltonien peut apparaître après quelques choix seulement. Une obstruction peut condamner immédiatement le graphe. Une organisation particulière des sommets peut permettre l’emploi d’un algorithme spécialisé.

Les mathématiciens et les informaticiens ne cherchent donc pas seulement une méthode universelle qui résoudrait miraculeusement tous les cas. Ils tentent aussi de reconnaître ce qui rend ce graphe-ci plus accessible qu’un autre.

Réduire la forêt avant de l’explorer

Avant de lancer une recherche, on peut commencer par examiner la structure du graphe.

Un sommet de degré inférieur à 2 interdit immédiatement l’existence d’un cycle hamiltonien. Un point d’articulation révèle également une faiblesse décisive : si sa suppression sépare le graphe en plusieurs morceaux, aucun cycle ne pourra traverser toutes les parties sans revenir plusieurs fois par ce même sommet.

D’autres raisonnements permettent de détecter des séparations plus discrètes, des groupes de sommets trop faiblement reliés au reste du graphe ou des arêtes qui deviendraient nécessairement incompatibles avec un cycle unique.

Ces observations ne donnent pas toujours la réponse complète. Elles permettent néanmoins de réduire l’espace de recherche.

Une arête peut être déclarée obligatoire. Une autre peut être interdite. Certaines branches peuvent être abandonnées avant même que le parcours ne commence réellement.

La forêt reste immense, mais une partie de ses chemins vient d’être fermée.

Faire les choix les plus contraints en premier

Lorsque l’exploration devient nécessaire, l’ordre des choix joue un rôle déterminant.

Un algorithme naïf peut sélectionner les sommets dans l’ordre où ils apparaissent dans les données. Une stratégie plus fine consiste à commencer par les zones les plus contraintes du graphe.

Un sommet qui ne possède que deux voisins n’offre aucune liberté dans un cycle hamiltonien : ses deux arêtes devront nécessairement appartenir au cycle. À l’inverse, un sommet relié à presque tous les autres peut généralement attendre.

En traitant d’abord les décisions les moins flexibles, on espère provoquer rapidement l’un des deux événements utiles :

• une contrainte forte s’intègre correctement dans le cycle ;
• une contradiction apparaît et condamne aussitôt la branche.

Cette démarche ne garantit pas que le bon parcours sera trouvé immédiatement. Elle augmente les chances que les mauvaises pistes révèlent leur faiblesse avant d’avoir mobilisé trop de calculs.

C’est une heuristique : une règle raisonnable, souvent efficace, mais qui ne constitue ni une preuve ni une garantie absolue.

Échanger de la mémoire contre du temps

Le retour sur trace oublie facilement le passé. Deux branches différentes peuvent conduire au même sous-problème : un sommet courant identique et un même ensemble de sommets restant à visiter. Sans précaution, le programme risque alors de résoudre plusieurs fois exactement la même situation.

La programmation dynamique cherche à éviter cette répétition.

Elle conserve en mémoire les sous-problèmes déjà rencontrés. Lorsqu’une configuration réapparaît, le programme peut réutiliser le résultat précédent au lieu de recommencer toute l’exploration.

Pour le problème hamiltonien, cette idée permet de construire des algorithmes exacts beaucoup plus efficaces que l’examen de toutes les permutations. Leur temps de calcul reste exponentiel, mais l’amélioration est considérable.

On ne visite plus aveuglément chaque ordre possible. On regroupe les parcours qui conduisent au même état.

La programmation dynamique ne fait pas disparaître l’explosion combinatoire.
Elle évite qu’elle se répète inutilement.

Cette économie possède cependant un prix : la mémoire nécessaire peut devenir très importante. Une méthode plus rapide n’est donc pas toujours une méthode légère.

Accepter parfois une bonne solution

Dans certaines applications, la question posée n’est pas exactement celle du cycle hamiltonien.

On ne cherche pas seulement un parcours passant une fois par chaque lieu. On souhaite également minimiser une distance, un coût ou une durée. C’est notamment le cas du célèbre problème du voyageur de commerce.

Trouver la meilleure tournée possible peut devenir hors de portée lorsque le nombre de sommets augmente. Mais une tournée excellente, même si son optimalité absolue n’est pas démontrée, peut déjà être très utile.

Les heuristiques et les algorithmes d’approximation changent alors l’objectif. Ils ne promettent plus toujours la solution parfaite. Ils cherchent une solution suffisamment bonne dans un temps raisonnable.

Cette distinction est essentielle dans la pratique.

En théorie, on demande souvent la certitude.
Dans la réalité, on demande parfois surtout une réponse exploitable.

Pour un problème de livraison, une tournée réalisable en quelques secondes et presque optimale peut être préférable à une tournée parfaitement optimale obtenue plusieurs années plus tard.

Il faut toutefois rester précis : pour le cycle hamiltonien sous sa forme classique, une réponse approximative n’a guère de sens. Un parcours visite tous les sommets ou ne les visite pas. L’approximation devient pertinente lorsque l’on ajoute un objectif mesurable, comme la longueur totale d’une tournée.

Des familles de graphes plus accueillantes

La NP-complétude concerne les graphes quelconques. Dès que l’on impose une structure particulière, la situation peut changer.

Les graphes peuvent être planaires, bipartis, très peu denses, construits selon une règle géométrique ou limités par certains paramètres. Ces contraintes ne rendent pas automatiquement le problème facile, mais elles fournissent des informations supplémentaires que les algorithmes peuvent exploiter.

On peut également chercher à isoler un paramètre réellement responsable de la difficulté : le nombre de sommets de fort degré, la taille d’une séparation, la largeur de certaines décompositions ou le nombre de choix véritablement ambigus.

Un graphe comportant beaucoup de sommets n’est pas nécessairement difficile si son organisation reste simple. À l’inverse, un graphe plus petit peut concentrer un grand nombre de décisions étroitement dépendantes.

La taille visible du dessin ne raconte donc qu’une partie de l’histoire.

Le pire cas n’est pas le cas quotidien

La théorie de la complexité examine ce qui peut arriver dans les situations les plus défavorables. Elle cherche une garantie valable pour tous les graphes, y compris ceux qui ont été spécialement construits pour résister aux algorithmes.

Les graphes rencontrés dans une application réelle ne sont pas toujours aussi hostiles.

Un réseau routier possède une géographie. Un emploi du temps contient des contraintes répétitives. Un circuit électronique suit des règles de conception. Ces structures peuvent être exploitées, même lorsqu’elles ne suffisent pas à rendre le problème facile au sens théorique.

Les solveurs modernes combinent ainsi plusieurs armes :

• prétraitements structurels ;
• propagation des contraintes ;
• retour sur trace ;
• heuristiques de choix ;
• mémorisation des sous-problèmes ;
• formulations logiques ou linéaires confiées à des solveurs spécialisés.

Aucune de ces méthodes ne détruit à elle seule la NP-complétude. Ensemble, elles permettent pourtant de résoudre des instances qui seraient totalement inaccessibles à une exploration brute.

Voilà le paradoxe.

Le problème hamiltonien reste difficile dans toute sa généralité. Nous ne connaissons aucune recette garantissant une résolution rapide de tous les graphes. Pourtant, nous savons résoudre de nombreux cas, parfois très grands, parce que nous apprenons à reconnaître leur structure et à concentrer l’effort là où se trouvent les véritables choix.

Nous n’avons pas trouvé de chemin permettant d’éviter toutes les forêts.
Nous avons appris à mieux lire les cartes.

Le silence des théorèmes n’est donc pas la fin de l’enquête.

C’est le moment où commencent l’algorithmique, les heuristiques et l’art de choisir les combats que l’on peut gagner.

Conclusion : explorer sans se perdre

Au début de cet épisode, les théorèmes venaient de se taire.

Dirac et Ore ne garantissaient plus l’existence d’un cycle. Aucune obstruction évidente ne permettait davantage d’en proclamer l’impossibilité. Il ne restait qu’un graphe et cette consigne apparemment simple : visiter chaque sommet exactement une fois avant de revenir au point de départ.

Nous avons alors pénétré dans la forêt des choix.

Chaque déplacement pris isolément semblait facile. Il suffisait de sélectionner un sommet voisin encore disponible. Mais ces décisions locales devaient rester compatibles jusqu’à la dernière étape. Une branche prometteuse pouvait échouer tout près du but et obliger l’algorithme à revenir sur des choix effectués bien plus tôt.

Quelques sommets supplémentaires suffisaient à faire apparaître des millions, puis des milliards de parcours possibles. Le retour sur trace permettait d’abandonner certaines pistes avant leur terme, les heuristiques orientaient la recherche et la programmation dynamique évitait de résoudre plusieurs fois les mêmes sous-problèmes.

La théorie de la complexité

Pour autant, aucune de ces méthodes ne garantit aujourd’hui une résolution rapide de tous les graphes.

Cette résistance nous a conduits jusqu’à la théorie de la complexité. Vérifier un cycle déjà proposé est une opération simple. Le découvrir peut demander une exploration considérable. Le problème de décision associé au cycle hamiltonien appartient ainsi à la famille des problèmes NP-complets, au cœur de la question toujours ouverte :

P = NP ?

Mais la NP-complétude n’est pas une condamnation.

Elle ne signifie pas que tous les graphes sont difficiles, ni que toute recherche est vouée à l’échec. Elle indique qu’aucune méthode rapide valable dans tous les cas n’est actuellement connue. Entre la facilité de certains exemples et la dureté du pire cas s’étend tout le territoire de l’algorithmique : reconnaître les structures favorables, exploiter les contraintes, couper les branches inutiles et choisir intelligemment l’ordre de l’exploration.

Euler nous avait appris à diagnostiquer un parcours.
Hamilton nous oblige à l’explorer.
L’algorithmique nous apprend à ne pas tout explorer.

Pour l’instant, nous n’avons demandé au cycle qu’une seule chose : exister.

Un parcours passant par tous les sommets suffisait, quelle que soit sa longueur. Un cycle court, un cycle interminable, un trajet élégant ou un détour absurde étaient placés sur un pied d’égalité.

Dans les situations concrètes, cette indifférence disparaît rapidement.

Lorsqu’un livreur doit visiter plusieurs villes, lorsqu’une machine doit effectuer une série d’opérations ou lorsqu’un circuit doit relier différents composants, trouver un parcours ne suffit plus. Il faut réduire la distance, le temps, la consommation ou le coût.

Une nouvelle question apparaît alors :

Parmi tous les cycles possibles, lequel est le meilleur ?

Le problème hamiltonien vient de changer de visage.

Dans le prochain épisode, « [5/6] Du cycle hamiltonien au voyageur de commerce », notre explorateur ne cherchera plus seulement à rentrer chez lui après avoir visité chaque ville. Il voudra le faire en empruntant la tournée la plus courte possible.

La forêt des choix n’a pas disparu.

Désormais, il faudra en comparer tous les chemins.