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