Problème de l'isomorphisme de graphes

Un isomorphisme ${\displaystyle f}$ d'un graphe G vers un graphe H est une bijection de l'ensemble des sommets de G dans l'ensemble des sommets de H, qui respecte les arêtes, c'est-à-dire : ${\displaystyle (u,v)}$ est une arête dans G si et seulement si ${\displaystyle (f(u),f(v))}$ est une arête dans H.

Le problème de l'isomorphisme de graphes est le problème de décision suivant :

• Entrée : G et H, deux graphes
• Question : G et H sont-ils isomorphes ?

Summarize Timeline Fact Check

Dans le cas général, plusieurs approches algorithmiques existent^[3]. 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^[4] et cela ne réduit pas toujours l'espace de recherche^[5]. 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^[6].

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^[7].

Jusqu'en 2015, le meilleur algorithme théorique connu était dû à Luks et Zemlyachenko, et a une complexité^[8] 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^[9].

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

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

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

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^[18].

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^[2] 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^[19] et est largement discuté quant à son impact sur la hiérarchie des complexités^{[20],[21],[22]}.

É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.^[23].

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^[24].

Plus précisément, le théorème de Boppana, Håstad et Zachos^[25] 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^[26].