[go: up one dir, main page]
Aller au contenu

Problème de l'isomorphisme de graphes

Un article de Wikipédia, l'encyclopédie libre.
Le problème est de savoir si deux graphes sont les mêmes.

En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets.

Ce problème est particulièrement important en théorie de la complexité, plus particulièrement pour le problème P=NP. En effet, le problème de l'isomorphisme de graphes est l'un des problèmes de NP, pour lequel on ne connaît ni d'algorithme en temps polynomial ni de preuve de NP-complétude. On le soupçonne être un problème NP-intermédiaire[réf. souhaitée]. Cependant le problème peut être résolu en temps polynomial pour certaines classes de graphes, par exemple les graphes planaires ou les graphes de degré borné et en temps quasi-polynomial pour le cas général[1]. Ce problème peut-être vu comme une restriction du problème de l'isomorphisme de sous-graphes. où les graphes G et H ont le même nombre de sommets.

En pratique, l'isomorphisme de graphes est utilisé en chimie pour classer les molécules.

Définitions

[modifier | modifier le code]

Un isomorphisme 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 : est une arête dans G si et seulement si 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 ?

Algorithmique

[modifier | modifier le code]

Cas général

[modifier | modifier le code]

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 (où n est le nombre de nœuds de l'un des graphes). Fin 2015, Babai a proposé un algorithme pseudo-polynomial (en ) ; 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].

Cas particulier

[modifier | modifier le code]

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

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 dans le cas d'une largeur d'arbre bornée par k[17].

Complexité

[modifier | modifier le code]

Entre P et NP

[modifier | modifier le code]

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

La classe GI

[modifier | modifier le code]

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

Relations avec les autres classes

[modifier | modifier le code]

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 , ce qui a comme corollaire l'affirmation précédente[25].

Applications

[modifier | modifier le code]

Preuves sans diffusion de connaissance

[modifier | modifier le code]

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 itérations, un mensonge éventuel n'a donc qu'une probabilité de 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].

Chimie

[modifier | modifier le code]
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].

Notes et références

[modifier | modifier le code]
  1. ↑ a et b László Babai Graph Isomorphism in Quasipolynomial Time sur ArXiV.org
  2. ↑ Cette partie est inspirée de Fortin 1996.
  3. ↑ Cette approche est parfois décrite comme de la magie noire, du fait des nombreux paramètres à régler.
  4. ↑ Derek G. Corneil et David G. Kirkpatrick, « A theoretical analysis of various heuristics for the graph isomorphism problem », SIAM Journal on Computing, vol. 9, no 2,‎ {1980}, p. 281-297
  5. ↑ Brendan D. McKay, « Practical graph isomorphism », Congressus Numerantium, vol. 30,‎ , p. 45-87 (lire en ligne).
  6. ↑ Vikraman Arvind, « The Weisfeiler-Lehman Procedure : The Computational Complexity Column », Bulletin of the EATCS, no 120,‎ (lire en ligne).
  7. ↑ Graph isomorphism sur de Complexity Garden (Complexity Zoo).
  8. ↑ László Babai, « Graph isomorphism in quasipolynomial time [extended abstract] », Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016, Association for Computing Machinery (ACM),‎ , p. 684-697 (ISBN 9781450341325, DOI 10.1145/2897518.2897542).
  9. ↑ Paul J. Kelly, « A congruence theorem for trees », Pacific J. Math, vol. 7,‎ , p. 961-968
  10. ↑ Kellogg S. Booth et George S. Lueker, « A linear time algorithm for deciding interval graph isomorphism », Journal of the ACM, vol. 26, no 2,‎ , p. 183-195 (DOI 10.1145/322123.322125).
  11. ↑ Charles J. Colbourn, « On testing isomorphism of permutation graphs », Networks, vol. 11,‎ , p. 13–21 (DOI 10.1002/net.3230110103).
  12. ↑ John E. Hopcroft et Jin-Kue Wong, « Linear time algorithm for isomorphism of planar graphs », dans Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, (DOI 10.1145/800119.803896), p. 172–184
  13. ↑ Gary Miller, « Isomorphism testing for graphs of bounded genus », dans Proceedings of the 12th Annual ACM Symposium on Theory of Computing, (ISBN 0-89791-017-6, DOI 10.1145/800141.804670), p. 225-235.
  14. ↑ Voir Eugene M. Luks, « Isomorphism of graphs of bounded valence can be tested in polynomial time », Journal of Computer and System Sciences, vol. 25,‎ , p. 42-65 (DOI 10.1016/0022-0000(82)90009-5). Cet article a permis à Eugene Luks (en) de recevoir le prix Fulkerson en 1985. Une description de l'idée de l'algorithme peut être trouvé dans Fortin 1996, section 2.3.
  15. ↑ Fortin 1996
  16. ↑ Par exemple J. Jaja et S.R. Kosaraju, « Parallel algorithms for planar graph isomorphism and related problems », IEEE transactions on circuits and systems, vol. 35, no 3,‎ , p. 304-311 et cité dans Fortin 1996
  17. ↑ « Graph Isomorphism on graphs of bounded treewidth », sur Banach's Algorithmic Corner (University of Warsaw),
  18. ↑ Quantum magazine Landmark Algorithm Breaks 30-Year Impasse
  19. ↑ What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem? sur le site mathoverflow.
  20. ↑ A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details sur le site Math ∩ Programming.
  21. ↑ Ken Regan, Dick Lipton, « A Little More on the Graph Isomorphism Algorithm », Gödel's Lost Letter and P-NP, (consulté le ).
  22. ↑ Pour une liste plus fournie et les références de ces exemples, voir Zemlyachenko, Korneenko et Tyshkevich 1985.
  23. ↑ (en) La classe GI sur le Complexity Zoo
  24. ↑ Ravi B. Boppana, Johan Håstad et Stathis Zachos, « Does co-NP Have Short Interactive Proofs? », Inf. Process. Lett., vol. 25, no 2,‎ , p. 127-132
  25. ↑ Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 10.2.5 (« Le problème de l'isomorhisme de graphes »)
  26. ↑ a et b Cours du Master parisien de recherche en informatique (MPRI) : [1]
  27. ↑ a et b Goldreich, Micali et Wigderson 1991.
  28. ↑ Il est cependant nécessaire que G n'appartienne pas à une classe de graphes pour lesquelles on sait résoudre efficacement le problème.
  29. ↑ John W. Raymond, Peter Willett: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. Journal of Computer-Aided Molecular Design 16(7): 521-533 (2002)

Bibliographie

[modifier | modifier le code]
  • Scott Fortin, The graph isomorphism problem (Technical Report 96-20), University of Alberta, Edomonton, Alberta, Canada, (lire en ligne)
  • Ronald C. Read et Derek G. Corneil, The graph isomorphism disease, vol. 1, (lire en ligne), chap. 4, p. 339-363
  • V. N. Zemlyachenko, N. M. Korneenko et R. I. Tyshkevich, « Graph isomorphism problem », Journal of Mathematical Sciences, vol. 29, no 4,‎ , p. 1426-1481 (DOI 10.1007/BF02104746)
  • Samir Datta, Nutan Limaye, Prajakta Nimbhorkar et Thomas Thierauf, « Planar Graph Isomorphism Is in Log-Space », ACM Transactions on Computation Theory, vol. 14, no 2,‎ , p. 8:1–8:33 (DOI 10.1145/3543686 Accès libre, lire en ligne, consulté le )
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Problème_de_l%27isomorphisme_de_graphes&oldid=217578856 ».