Prueba de que el problema de decisión de camarilla es NP-Complete | conjunto 2

Requisito previo: NP-Completo , problema de camarilla .

Una camarilla en un gráfico es un conjunto de vértices donde cada vértice comparte un borde con todos los demás vértices. Así, una camarilla en un grafo es un subgrafo que es un grafo completo.
Problema: Dada una gráfica G(V, E) y un entero K, el problema es determinar si la gráfica contiene una camarilla de tamaño K.

Explicación:
una instancia del problema es una entrada especificada para el problema. Una instancia del problema Clique es un grafo G (V, E) y un entero positivo K, y el problema es comprobar si existe un clique 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, simplemente 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 .

En este artículo, demostraremos que el problema de detección de camarilla es NP-Completo con la ayuda del problema de conjuntos independientes , que es NP-Completo. Consulte Prueba de que el problema de decisión de camarilla es NP-Completo , para la prueba con la ayuda del Problema de satisfacción booleano .

1. El problema de Clique está en NP
   Si cualquier 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), lo haremos poder 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 a la camarilla. Podemos validar esta solución comprobando que cada par de vértices pertenecientes a la solución son adyacentes, simplemente comprobando que comparten arista entre sí. Esto se puede hacer en tiempo polinomial, es decir O(V +E) usando la siguiente estrategia para el gráfico G(V, E) :

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

2. El problema de Clique es NP-Difícil
   Para probar que el problema de Clique es NP-Difícil, tomamos la ayuda de un problema que ya es NP-Difícil y mostramos que este problema se puede reducir al problema de Clique.
   Para ello, consideramos el problema de Conjuntos Independientes , que es NP-Completo (y por lo tanto NP-Hard ). Cada instancia del problema de conjuntos independientes 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’) y K’ del problema Clique. Construiremos el grafo G’ con las siguientes modificaciones:
   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 grafo G’ es el grafo complementario de G. El tiempo necesario para calcular el grafo complementario G’ requiere un recorrido por todos los vértices y aristas .
   Complejidad temporal: O (V+E)

   Ahora probaremos que el problema de calcular la camarilla de hecho se reduce al cálculo del conjunto independiente. 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 lo tanto, el grafo G tendrá una camarilla de tamaño K.

Así, podemos decir que hay una camarilla de tamaño K en el grafo G si hay un conjunto independiente de tamaño K en G’ (gráfico del complemento). Por lo tanto, cualquier instancia del problema de la camarilla se puede reducir a una instancia del problema del conjunto independiente. Por lo tanto, el problema de la camarilla es NP-Hard.

Conclusión:

Por lo tanto, el problema de decisión de camarilla es NP-Completo