Prueba de que el conjunto independiente en la teoría de grafos es NP completo

Requisito previo: NP-Completo , Conjunto independiente .

Un Conjunto Independiente S del gráfico G = (V, E) es un conjunto de vértices tales que no hay dos vértices en S adyacentes entre sí. Consta de vértices no adyacentes.

Problema: Dada una gráfica G(V, E) y un entero k, el problema es determinar si la gráfica contiene un conjunto independiente de vértices de tamaño >=k.
Explicación:
una instancia del problema es una entrada especificada para el problema. Una instancia del problema del conjunto independiente es un gráfico G (V, E) y un entero positivo k, y el problema es verificar si existe un conjunto independiente de tamaño k en G. Dado que un problema NP-Completo, por definición, es un problema que está tanto en NP como en NP-difícil, la prueba de la afirmación de que un problema es NP-Completo consta de dos partes:

1. El problema en sí está en la clase NP.
2. Todos los demás problemas en la clase NP pueden ser reducibles en tiempo polinomial a eso.
   (B es reducible en tiempo polinomial a C se denota como )

Si solo se cumple la segunda condición, el problema se llama NP-Hard .

Pero no es posible reducir cada problema NP a otro problema NP para mostrar su NP-Completitud todo el tiempo. Es por eso que si queremos mostrar que un problema es NP-Completo, solo mostramos que el problema está en NP y cualquier problema NP-Completo es reducible a eso, entonces hemos terminado, es decir, si B es NP-Completo y para C en NP , entonces C es NP-Completo.

1. El conjunto independiente es NP
   Si algún problema está en NP, entonces, dado un ‘certificado’, que es una solución al problema y una instancia del problema (un gráfico G y un entero positivo k, en este caso), seremos capaz de verificar (comprobar si la solución dada es correcta o no) el certificado en tiempo polinomial.
   El certificado es un subconjunto V’ de los vértices, que comprende los vértices pertenecientes al conjunto independiente. Podemos validar esta solución comprobando que cada par de vértices pertenecientes a la solución no son adyacentes, simplemente comprobando que no comparten arista entre sí. Esto se puede hacer en tiempo polinomial, es decir O(V +E) usando la siguiente estrategia del gráfico G(V, E):

   flag=true
   For every pair {u, v} in the subset V’:
       Check that these two don’t
       have an edge between them
       If there is an edge,
       set flag to false and break
   If flag is true:
       Solution is correct
   Else:
       Solution is incorrect
   

2. El conjunto independiente es NP-Hard.
   Para probar que el problema de conjuntos independientes es NP-Hard, realizaremos una reducción de un problema NP-Hard conocido a este problema. Realizaremos una reducción a partir de la cual el Problema de la Camarilla se puede reducir al problema del Conjunto Independiente.
   Cada instancia del problema de la camarilla que consta del gráfico G (V, E) y un número entero k se puede convertir en el gráfico requerido G’ (V’, E’) yk’ del problema del conjunto independiente. Construiremos el grafo G’ de la siguiente forma:
   

   V’ = V, es decir, todos los vértices del grafo G son parte del grafo G’
   E’ = complemento de las aristas E, es decir, las aristas que no están presentes en el grafo original G.

   El gráfico G’ es el gráfico complementario de G. El tiempo requerido para calcular el gráfico complementario G’ requiere un recorrido por todos los vértices y aristas. La complejidad temporal de esto es O (V+E).
   Ahora demostraremos que el problema de calcular el conjunto independiente se reduce al cálculo de la camarilla. La reducción puede probarse mediante las siguientes dos proposiciones:

   • Supongamos que el gráfico G contiene una camarilla de tamaño k. La presencia de clique implica que hay k vértices en G, donde cada uno de los vértices está conectado por una arista con los vértices restantes. Esto muestra además que, dado que estos bordes están contenidos en G, no pueden estar presentes en G’. Como resultado, estos k vértices no son adyacentes entre sí en G’ y por lo tanto forman un Conjunto Independiente de tamaño k.
   • Suponemos que el grafo complementario G’ tiene un conjunto independiente de vértices de tamaño k’. Ninguno de estos vértices comparte una arista con ningún otro vértice. Cuando complementamos el gráfico para obtener G, estos k vértices compartirán un borde y, por lo tanto, se volverán adyacentes entre sí. Por tanto, el grafo G tendrá un clique de tamaño k.

Thus, we can say that there is an independent set of size k in graph G if there is a clique of size k in G’ (complement graph). Therefore, any instance of the independent set problem can be reduced to an instance of the clique problem. Thus, the independent set is NP-Hard.

Conclusión:
dado que el problema del conjunto independiente es tanto NP como NP-Difícil, es un problema NP-Completo.

Para más detalles, consulte:
Diseño y Análisis de Algoritmos .