Prueba de que el problema de isomorfismo de subgrafo es NP-Completo

Problema de isomorfismo de subgrafos : Tenemos dos grafos no dirigidos G ₁ y G ₂ . El problema es comprobar si G ₁ es isomorfo a un subgrafo de G ₂ .

Isomorfismo de grafos: dos grafos A y B son isomorfos entre sí si tienen el mismo número de vértices y aristas, y se conserva la conectividad de las aristas. Existe una biyección entre los conjuntos de vértices de los gráficos A y B. Por lo tanto, dos vértices u, v son adyacentes entre sí en A si y solo si f(u), f(v) son adyacentes en B (f es un biyección).

Para probar que un problema es NP-Completo, tenemos que demostrar que pertenece a las clases NP y NP-Hard. (Dado que los problemas NP-Completos son problemas NP-Difíciles que también pertenecen a NP) El problema de isomorfismo de subgrafo pertenece a NP: si un problema pertenece a la clase NP, entonces debería tener verificabilidad en tiempo polinomial. Dado un certificado, deberíamos poder verificar en tiempo polinomial si es una solución al problema.

Prueba:

1. Certificado: Sea G un subgrafo de G ₂ . También conocemos el mapeo entre los vértices de G ₁ y G.
2. Verificación: Tenemos que comprobar si G ₁ es isomorfo a G o no. (i) Verificar si el mapeo es una biyección y (ii) Verificar si, para cada arista (u, v) en G ₁ , hay una arista (f(u), f(v)) presente en G toma tiempo polinomial .

Por lo tanto, el problema de isomorfismo de subgrafos tiene verificabilidad en tiempo polinomial y pertenece a la clase NP.

El problema de isomorfismo de subgrafos pertenece a NP-Hard: un problema L pertenece a NP-Hard si cada problema NP es reducible a L en tiempo polinomial. Para demostrar que el Problema de isomorfismo de subgrafos (S) es NP-Difícil, tratamos de reducir un problema NP-Difícil ya conocido a S para una instancia particular. Si esta reducción es posible en tiempo polinomial, entonces S también es un problema NP-Hard. Por lo tanto, reduzcamos el problema de decisión de camarilla (C) que es NP-Completo (por lo tanto, todos los problemas en NP se pueden reducir a C en tiempo polinomial) al problema de isomorfismo de subgrafo. Si esta reducción es posible en tiempo polinomial, cada problema NP puede reducirse a S en tiempo polinomial, demostrando así que S es NP-Hard.

Prueba: Demostremos que el Problema de Decisión de Clique se reduce al Problema de Isomorfismo de Subgrafo en tiempo polinomial.

Sea la entrada al problema de decisión de la camarilla (G, k). La salida es verdadera si el gráfico G contiene una camarilla de tamaño k (una camarilla de tamaño k es un subgráfico de G). Sea G1 un gráfico completo de k vértices y G ₂ sea G, donde G ₁ , G ₂ son entradas al problema de isomorfismo de subgrafo. Observamos que k <=n, donde n es el número de vértices en G (=G ₂ ). Si k>n, entonces una camarilla de tamaño k no puede ser un subgrafo de G. El tiempo necesario para crear G ₁ es O(k ² ) = O(n ² ) [ya que k<=n] como el número de aristas en una gráfica completa de tamaño k = ^k C ₂ = k*(k-1)/2. G tiene una camarilla de tamaño k, si y solo si G1 es un subgrafo de G ₂(dado que G ₁ en sí mismo es un subgrafo de G ₂ y cada gráfico es isomorfo a sí mismo, el resultado del problema de isomorfismo de subgrafo es verdadero. Por lo tanto, G ₁ es isomorfo a un subgrafo de G ₂ ). Por lo tanto, si el problema de decisión de camarilla es verdadero, el problema de isomorfismo de subgrafo es verdadero y viceversa. Por lo tanto, el problema de decisión de camarilla se puede reducir al problema de isomorfismo de subgrafo en tiempo polinomial para una instancia particular.

Por lo tanto, el problema de isomorfismo de subgrafos es un problema NP-difícil

Conclusión:
El problema de isomorfismo de subgrafos es NP y NP-Hard. Por lo tanto, el problema de isomorfismo de subgrafos es NP-Completo .