Problema de isomorfismo de subgrafos

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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(G1, G2)
Entrada: Dos grafos G1 y G2.
Pregunta: Es G1 isomorfo a un subgrafo de G2?

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 G1 una clique de tamaño 3 a n, y G2 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 polinomial colapsa, así que se supone que no debería ser así.

Véase también[editar]

Referencias[editar]