Problème de l'isomorphisme de graphes

Dans le cas général, plusieurs approches algorithmiques existent[2]. Les trois plus classiques sont :

• L'utilisation d'invariants de sommets, qui sont des entiers associés aux sommets tels que deux sommets équivalents de deux graphes isomorphes ont la même valeur. On peut citer par exemple le degré, la distance à un sommet particulier, la taille de la clique maximum contenant le sommet etc. Si les deux graphes n'ont pas les mêmes invariants ils sont différents. On peut raffiner ce genre d'argument, mais il reste toujours la difficulté du choix des invariants[3] et cela ne réduit pas toujours l'espace de recherche[4]. Cependant si les deux graphes n'ont pas des structures proches, comme c'est le cas pour certaines applications, il est très rapide de le détecter avec ce genre de techniques.

• La construction incrémentale de l'isomorphisme, en ajoutant des sommets peu à peu, avec retour sur trace (backtracking).

• Le calcul pour chaque graphe d'un identifiant canonique. Cette approche permet une utilisation de résultats d'algèbre générale. Un exemple est l'algorithme nauty de McKay[5].

On peut aussi citer la méthode de Weisfeiler et Lehman qui consiste en un raffinement de coloration et qui est lié à de nombreux domaines de l'informatique théorique[6].

Jusqu'en 2015, le meilleur algorithme théorique connu était dû à Luks et Zemlyachenko, et a une complexité[7] en ${\displaystyle 2^{O\left({\sqrt {n\log(n)}}\right)}}$ (où n est le nombre de nœuds de l'un des graphes). Fin 2015, Babai a proposé un algorithme pseudo-polynomial (en ${\displaystyle 2^{log(n)^{O\left(1\right)}}}$) ; l'article a attiré l'attention de la communauté de l'informatique théorique, et a obtenu le best paper award de la conférence STOC 2016[8].

Le problème peut-être résolu en temps polynomial sur de nombreuses classes de graphes, parmi lesquelles :

• Les arbres[9], les graphes d'intervalles[10], les graphes de permutation[11].
• Les graphes planaires[12], et plus généralement les graphes de genre borné[13].
• Les graphes de degré borné[14].

Une partie de ces algorithmes ne peuvent pas être utilisés dans la pratique du fait de grandes constantes multiplicatives[15], mais dans certains cas ayant des applications importantes, comme pour les graphes planaires, il existe des algorithmes et des implémentations efficaces[16].

La plupart des algorithmes sur des classes ayant un paramètre, comme le degré borné ou la largeur d'arbre, ont des complexités dépendant de manière exponentielle de ce paramètre. Cet aspect est étudié en complexité paramétrée. On peut par exemple montrer une complexité en temps de la forme ${\displaystyle 2^{O(k^{5}log(k))}n^{5}}$ dans le cas d'une largeur d'arbre bornée par k[17].

Le problème de l'isomorphisme de graphe est dans la classe NP, mais il est l'un des seuls problèmes connus de cette classe, avec la décomposition en produit de facteurs premiers à ne pas avoir été prouvé polynomial ou NP-complet. En ce sens c'est un problème intéressant pour le problème P=NP.

En décembre 2015 László Babai propose[1] un algorithme quasi-polynomial pour résoudre le problème, faisant largement descendre la borne de complexité. Ce résultat émerveille la communauté scientifique de l'algorithmique[18] et est largement discuté quant à son impact sur la hiérarchie des complexités[19] - [20] - [21].

Étant donné ce statut particulier du problème, la classe GI (comme Graph Isomorphism) a été introduite, et consiste en tous les problèmes ayant une réduction polynomiale au problème de l’isomorphisme de graphe. On parle ainsi de problème GI-difficile et GI-complet.

Parmi les problèmes GI-complets, on compte le problème de l’isomorphisme pour d'autres structures, comme les graphes orientés et les hypergraphes, et des cas particuliers du problème, par exemple l'isomorphisme sur des graphes réguliers, cordaux, etc.[22].

Le problème de l'isomorphisme de graphe est dans co-AM (une classe définie par les protocoles d'Arthur et Merlin), ainsi, si le problème est NP-complet alors la hiérarchie polynomiale s'écroule[23].

Plus précisément, le théorème de Boppana, Håstad et Zachos[24] donne que si co-NP est inclus dans AM, alors ${\displaystyle \Sigma _{2}^{p}=\Pi _{2}^{p}}$, ce qui a comme corollaire l'affirmation précédente[25].

Le problème de l'isomorphisme de graphe peut être utilisé pour concevoir des protocoles de preuve à divulgation nulle de connaissance[26] - [27]. On se place dans le cas où un individu A souhaite prouver à un autre individu B qu'il connaît une 3-coloration d'un certain graphe G mais sans vouloir en donner de coloration explicite. A va alors envoyer à B un graphe G' isomorphe à G, et B va choisir aléatoirement parmi deux options :

• demander à A une 3-coloration de G' ;
• demander à A un isomorphisme permettant de passer de G à G'.

Cette opération peut être répétée un grand nombre de fois en générant à chaque fois un nouveau graphe G'. Si A connaît effectivement une 3-coloration de G, il parviendra toujours à répondre à la demande de B, mais s'il ne dit pas la vérité le mensonge a à chaque itération une chance sur deux d'être découvert (car soit G' n'est pas isomorphe à G, soit A ne peut pas en donner de 3-coloration puisqu'il n'en connaît pas). Après ${\displaystyle n}$ itérations, un mensonge éventuel n'a donc qu'une probabilité de ${\displaystyle {\frac {1}{2^{n}}}}$ de ne pas être découvert.

De son côté, B ne peut déduire de 3-coloration de G ni à partir de celle de G' (car aucun algorithme polynomial permettant de retrouver G à partir de G' n'est connu dans le cas général[28]) ni ne peut calculer de 3-coloration de G' (car le problème de la 3-coloration est NP-complet). In fine B peut se convaincre que A connaît une 3-coloration de G, mais n'a aucun indice pour la construire lui-même.

Il est possible d'établir un tel protocole pour la solution à n'importe quel problème NP-complet relatif à un graphe[26], et comme il est possible par réduction de transformer tout problème NP-complet en un autre, il s'ensuit que l'on peut concevoir un tel protocole de vérification pour toute solution de problème NP-complet[27].

La formule topologique de la molécule Spinochrome E (en).

Les isomorphismes de graphes apparaissent notamment en chimie, où les molécules peuvent être vues comme des graphes étiquetés par des atomes (voir l'image ci-contre). L'un des objectifs est alors de classer les molécules dans des bases de données, en ayant une seule entrée pour chaque molécule quel que soit l'ordre des sommets, ce qui demande d'avoir une forme canonique et de gérer les structures isomorphes[29].