Problème de l'isomorphisme de sous-graphes

Soient ${\displaystyle G=(V_{G},E_{G})}$ et ${\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 ${\displaystyle G_{0}=(V_{0},E_{0})}$ , avec ${\displaystyle V_{0}\subseteq V_{G}}$ et ${\displaystyle E_{0}\subseteq E_{G}\cap (V_{0}\times V_{0})}$ , tel qu'il existe une bijection ${\displaystyle f:V_{0}\rightarrow V_{H}}$ telle que ${\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}}$  ? ».

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

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.