Problema de isomorfismo de subgrafos
# Problema de isomorfismo de subgrafos

En complejidad computacional, el Problema de isomorfismo de subgrafos, también a veces llamado Problema de matching de subgrafos, es un problema de decisión NP-completo, que formalmente, se define de la siguiente manera:

* $Isomorfismo-de-subgrafos(G_1,$ $G_2)$
* Entrada: Dos grafos $G_1$ y $G_2.$
* Pregunta: Es $G_1$ isomorfo a un subgrafo de $G_2?$

La NP-completitud del problema se demuestra mediante la reducción de este problema al Problema de la clique. Si el Problema de isomorfismo de subgrafos fuese polinomial, podría utilizarse para resolver el Problema de la clique, también en tiempo polinomial. Sea n el número de aristas de G, se puede ejecutar el problema de isomorfismo de subgrafos n-2 veces (siendo $G_1$ una clique de tamaño 3 a n, y $G_2$ siendo G) para encontrar el clique más grande en G.

Este problema es una generalización del posiblemente más sencillo Problema de isomorfismo de grafos, en el sentido que si este último es NP-completo, entonces la jerarquía polinómica colapsa, así que se supone que no debería ser así.

