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}}$ ? ».