Des problèmes de graphes faciles à comprendre mais difficiles à résoudre

Circuit de Hamilton. fdecomite/Flickr, CC BY

En informatique théorique, l’incertain est chose courante. Des centaines de problèmes ont un statut particulier : à ce jour, personne ne sait s’il existe, ou pas, des méthodes – des algorithmes – efficaces pour les résoudre. Comble de la frustration : ceux dont la résolution est un casse-tête mais qui s’expriment de manière simple ! C’est le cas de plusieurs problèmes fondés sur des objets simples, les graphes.

Rassurez-vous ! même si vous n’êtes pas expert en graphes, vous arriverez probablement à comprendre les énoncés que nous allons dérouler. Ces problèmes, qui ressemblent à des jeux mathématiques, sont pourtant au cœur de l’informatique théorique. Et personne ne sait les résoudre de manière exacte avec un algorithme efficace (une notion qui est précisément définie dans le domaine de la complexité algorithmique). Attention : l’objectif est de proposer ici un algorithme qui résoudrait l’un de ces problèmes de manière optimale et de manière efficace (avec un temps de calcul « raisonnable »), pour n’importe quelle donnée d’entrée, un graphe en l’occurrence. Les chercheurs essaient depuis des décennies d’en mettre au point, sans succès à ce jour. Il est conjecturé que ce n’est pas possible mais nous n’avons aucune preuve. Résoudre ces problèmes avec des algorithmes efficaces – et des centaines d’autres équivalents permettrait d’améliorer la performance ou la précision de nombreux logiciels.

Pour mémoire, un graphe est composé d’un ensemble d’éléments (les sommets) dont certains sont reliés par des liaisons (les arêtes). En voici un, en image, composé des sommets a,b,c,d,e,f,g,h – représentés sous forme de cercles – et d’arêtes – dessinées sous forme de traits.

Auteur, Author provided

Examinons maintenant quelques énoncés de problèmes, difficiles à résoudre (au sens indiqué plus haut), de théorie des graphes, illustrés pour vous aider à bien saisir les contraintes. Soit G un graphe quelconque.

  • Quel est le plus petit ensemble C de sommets de G tel que chaque arête a au moins une de ses deux extrémités dans C ? Un tel ensemble est nommé une couverture optimale des arêtes.
Dans cet exemple, les sommets a,c,e,f,h forment une couverture (chaque arête a bien au moins une extrémité qui est a,c,e,f ou h) de taille optimale (ce point est un petit peu plus difficile à démontrer). Auteur, Author provided
  • Quel est le plus petit ensemble D de sommets de G tel que chaque sommet en dehors de D est en liaison avec au moins un sommet de D ? Un tel D est un dominant optimal de G.
Dans cet exemple, les sommets a et e forment un dominant (chaque sommet en dehors de a et de e est en liaison avec a ou e ; on dit qu’il est dominé par a ou e) de taille optimale (car il n’y a pas de dominant contenant un seul sommet dans ce graphe). Auteur, Author provided
  • Une variante du problème précédent : quel est le plus petit ensemble T de sommets de G tel que chaque sommet de G (y compris ceux de T) est en liaison avec au moins un sommet de T ? Un tel T est un dominant total optimal de G.
Dans cet exemple, les sommets e,f,g forment un dominant total : chaque sommet, coloré ou pas, est en liaison avec (c’est-à-dire est dominé par) au moins un sommet e,f ou g. Notez que le dominant de la figure précédente (les sommets a et e) n’est pas un dominant total car ni e ni a ne sont dominés. Auteur, Author provided
  • Est-il possible, en partant de n’importe quel sommet r, de passer exactement une fois par chaque sommet de G, en traversant à chaque pas une liaison, en revenant sur r à la fin ? Un tel objet, s’il existe, est appelé un cycle hamiltonien.
Dans cet exemple, les arêtes en rouge forment un cycle hamiltonien et permettent de « faire le tour du graphe ». Auteur, Author provided
  • Quel est le plus grand ensemble S de sommets qui n’ont aucune liaison entre eux ? Un tel S est un stable de taille maximale de G.
Dans cet exemple, les trois sommets c,h,f sont indépendants les uns des autres et forment donc un stable. Il n’y en a pas de plus gros (mais il y en a d’autres de taille trois, par exemple a,f,d). Auteur, Author provided
  • Quel est le plus petit nombre de couleurs à utiliser pour que chaque sommet ait une couleur différente de celle des sommets avec lesquels il partage une liaison ? Ceci est connu sous le nom du problème de la coloration optimale.
Dans cet exemple, trois couleurs différentes sont nécessaires et suffisantes pour satisfaire les contraintes. C’est une coloration optimale de ce graphe. Auteur, Author provided

Résoudre la coloration optimale permettrait de créer des… plannings optimaux. Voici une vidéo pour en savoir plus sur la relation entre coloration et production de plannings.

Alors, comment s’en sortir ?

Cette impuissance à résoudre ces problèmes dont la description est simple est troublante. De nombreux travaux de recherche ont pour objectif de contourner cette difficulté… d’une manière ou d’une autre. Par exemple certaines heuristiques (comme le recuit simulé ou les algorithmes génétiques) peuvent donner, en pratique, des résultats intéressants. Mais il est en général impossible de prouver leur bon comportement (qui n’est absolument pas systématique).

Une autre approche est celle des algorithmes d’approximation : essayer de résoudre ces problèmes non pas de manière optimale mais avec des algorithmes efficaces qui peuvent garantir (de manière analytique, prouvée) la qualité de la solution produite par rapport à la solution optimale (que l’on ne connaît pas). Il peut sembler étonnant de pouvoir comparer le résultat d’un algorithme à quelque chose que l’on ne connaît pas ; c’est possible mais hélas pas pour tous les problèmes et ce n’est pas toujours très efficace. Un autre angle d’attaque est de résoudre le problème mais seulement pour des classes particulières de graphes.

Il reste encore sans doute beaucoup de travail à faire pour percer ce mystère qui a un intérêt théorique certain mais dont la résolution positive pourrait avoir un impact important sur la performance ou la précision des logiciels.

Les problèmes mentionnés dans cet article (et de nombreux autres) sont illustrés sur ma chaîne YouTube consacrée aux graphes. On peut aussi consulter le travail de Jean‑Paul Delahaye, mathématicien et vulgarisateur.