Problème de l'isomorphisme de sous-graphes

Le problème est de savoir si un graphe contient un autre graphe comme sous-graphe.

En informatique théorique, le problème de l'isomorphisme de sous-graphes est le problème de décision suivant : étant donnés deux graphes G et H, déterminer si G contient un sous-graphe isomorphe à H[1]. C'est une généralisation du problème de l'isomorphisme de graphes.

Définition

Soient G = ( V G , E G ) {\displaystyle G=(V_{G},E_{G})} et H = ( V H , E H ) {\displaystyle H=(V_{H},E_{H})} deux graphes. Le problème de décision de l'isomorphisme de sous-graphe est : « Est-ce qu'il existe un sous-graphe G 0 = ( V 0 , E 0 ) {\displaystyle G_{0}=(V_{0},E_{0})} , avec V 0 ⊆ V G {\displaystyle V_{0}\subseteq V_{G}} et E 0 ⊆ E G ∩ ( V 0 × V 0 ) {\displaystyle E_{0}\subseteq E_{G}\cap (V_{0}\times V_{0})} , tel qu'il existe une bijection f : V 0 → V H {\displaystyle f:V_{0}\rightarrow V_{H}} telle que ∀ v 1 , v 2 ∈ V 0 , ( v 1 , v 2 ) ∈ E G ⇔ ( f ( v 1 ) , f ( v 2 ) ) ∈ E H {\displaystyle \forall v_{1},v_{2}\in V_{0},(v_{1},v_{2})\in E_{G}\Leftrightarrow (f(v_{1}),f(v_{2}))\in E_{H}}  ? ».

Complexité

Le problème est NP-complet[2].

Réduction du problème de la clique

Le problème de la clique se réduit en temps polynomial au problème de l'isomorphisme de sous-graphe. Il suffit de prendre pour H {\displaystyle H} une k {\displaystyle k} -clique, dès lors, par définition le problème de l'isomorphisme de sous-graphes généralise le problème de la clique. Puisque le problème de la clique est NP-difficile, alors le problème de l'isomorphisme est NP-difficile.

Un autre réduction consiste à utiliser le problème du chemin hamiltonien, et a l'avantage de montrer que le problème est aussi difficile sur les graphes planaires[3].

Algorithme non-déterministe polynomial

Il existe un algorithme non-déterministe qui résout en temps polynomial le problème. L'algorithme consiste à prendre le sous-graphe G 0 {\displaystyle G_{0}} et une fonction f {\displaystyle f} aléatoirement, puis à vérifier si f {\displaystyle f} est un isomorphisme. Vérifier que f {\displaystyle f} est bien un isomorphisme se calcule en temps polynomial : il suffit de voir si tous les voisinages sont conservés par l'isomorphisme.

Relation à d'autres problèmes

Le problème de l'isomorphisme de sous-graphes est un problème plus général que le problème de l'isomorphisme de graphes, où on demande si G et H sont isomorphes. En effet, on peut décider l'isomorphisme de G et H et donnant (G, H) en entrée à un algorithme qui décide l'isomorphisme de sous-graphes.

Notes et références

  1. ↑ J. R. Ullmann, « An Algorithm for Subgraph Isomorphism », J. ACM, vol. 23, no 1,‎ , p. 31–42 (ISSN 0004-5411, DOI 10.1145/321921.321925, lire en ligne, consulté le )
  2. ↑ Ingo Wegener, Complexity Theory : Exploring the Limits of Efficient Algorithms, Springer, , 308 p. (ISBN 978-3-540-21045-0, lire en ligne), p. 81.
  3. ↑ Colin de la Higuera, Jean-Christophe Janodet, Émilie Samuel, Guillaume Damiand et Christine Solnon, « Polynomial algorithms for open plane graph and subgraph isomorphisms », Theoretical Computer Science, vol. 498,‎ , p. 76-99 (DOI 10.1016/j.tcs.2013.05.026, lire en ligne) « It is known since the mid-70’s that the isomorphism problem is solvable in polynomial time for plane graphs. However, it has also been noted that the subisomorphism problem is still NP-complete, in particular because the Hamiltonian cycle problem is NP-complete for planar graphs. »
  • icône décorative Portail de l'informatique théorique