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. C'est une généralisation du problème de l'isomorphisme de graphes.

Définition

Soient $G=(V_G,E_G)$ et $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)$, avec $V_0\subseteq V_G$ et $E_0\subseteq E_G\cap (V_0\times V_0)$, tel qu'il existe une bijection $f:V_0\to V_H$ telle que $\mathrm{\forall }{v}_1,v_2\in V_0,(v_1,v_2)\in E_G\iff (f(v_1),f(v_2))\in E_H$ ? ».

Complexité

Le problème est NP-complet.

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

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$ et une fonction $f$ aléatoirement, puis à vérifier si $f$ est un isomorphisme. Vérifier que $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.