Problema de isomorfismo de subgrafos

Problema de isomorfismo de subgrafos

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 G₁ una clique de tamaño 3 a n, y G₂ 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

• Isomorfismo de grafos

Referencias

• J. R. Ullmann: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
• Michael R. Garey y David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.4: GT48, pg.202.

Obtenido de "Problema de isomorfismo de subgrafos"