Demostrar que un problema formado por Clique y Conjunto Independiente es NP Completo

Prerrequisito: NP-Completeness , NP Class , Clique , Independent Set

Problema: dado un gráfico no dirigido G = (V, E) y un número entero K , determine si existeuna camarilla de tamaño K , así como un conjunto independiente (IS) de tamaño K. Demostrar que es un NP Completo.

Explicación:

Un Clique es un subgrafo de un grafo en el que todos los vértices están conectados, formando un grafo completo. El problema de decisión de camarilla implica determinar si existe o no una camarilla de tamaño K en el gráfico dado.

Un Conjunto Independiente S del gráfico G = (V, E) es una colección de vértices en el gráfico G = (V, E) donde no hay dos vértices adyacentes.

Dado que el problema Clique+IS es una combinación de ambos, Clique e Independent, se puede describir de la siguiente manera:

• Entrada – Gráfico G (V, E) y entero K
• Salida – Conjunto Clique e Independiente de talla K

Para probar un problema NP Completo, hay dos pasos involucrados:

1. Demostrar que el problema dado pertenece a la clase NP
2. Todos los demás problemas de la clase NP pueden ser reducibles en tiempo polinomial a ese problema. (Esta es la prueba de ser NP-Hard)

Ahora bien, no es posible reducir cada problema NP a otro problema NP para probar su integridad NP todo el tiempo. Es por eso que mostramos que cualquier problema NP completo conocido es reducible a ese problema en tiempo polinomial.

Prueba:

1.Clique+IS pertenece a la Clase NP:

Se dice que un problema está en la clase NP si la solución del problema se puede verificar en tiempo polinomial.

Dada una entrada G = (V, E) y un tamaño de conjunto de K , la respuesta es dos conjuntos: I (Conjunto independiente) y C (Conjunto de camarilla). Hay tres pasos para verificar la solución a este problema:

• Verificar Conjunto Independiente: Para todos los pares de vértices (x, y) tales que x, y ∈ I y (x, y) ∉ E . Esto tomaría O(n ² ) tiempo como | yo | = K y K ≤ n donde n es el número de vértices.
• Verifique Clique Set: Para todos los pares de vértices (x, y) tales que x, y ∈ C y (x, y) ∈ E . Esto tomaría O(n ² ) tiempo como |C| = K y K ≤ n donde n es el número de vértices.
• Verificar Tamaño de ambos conjuntos: Para verificar |I| = |C| = k toma O(1) tiempo.

Por lo tanto, la verificación de una solución para Clique+IS requiere como máximo O(n ² ) , que es de naturaleza polinomial, por lo que Clique+IS pertenece a la clase NP .

2. Clique + IS es un problema NP-Hard:

Ahora tenemos que demostrar que Clique + IS es al menos tan difícil como un problema NP-Completo conocido mediante la técnica de reducción. 

Aquí, el problema conocido será el problema de Clique, que ya se sabe que es NP-completo, que se explica en Prueba de que Clique es NP-Completo . 

Vamos a mostrar la reducción desde Clique -> Clique+IS. 

Sin embargo, también es posible mostrar la reducción como Conjunto Independiente -> Clique + IS donde se sabe que   Conjunto Independiente es un Problema NP-Completo .

Conversión de entrada: Necesitamos convertir la entrada de Clique a entrada a Clique+IS.

Clique toma un gráfico de entrada G = (V, E) y el parámetro K para establecer el tamaño. Para convertir la entrada de Clique a Clique+IS:

• Crearemos un gráfico como   G'(V’, E’) que será la copia del gráfico dado G = (V, E) . 
• Vamos a sumar los vértices del Conjunto Independiente I a la gráfica G’ tal que | yo | = K y K ≤ norte .

Entonces, el Gráfico G’ será el gráfico que tendrá todos los vértices y aristas del Gráfico G y los vértices del conjunto independiente I .

La creación de un nuevo gráfico tomará O(|n| + |m|) tiempo. Agregar nuevos vértices tomará O(n) . Desde  |yo| = K y K ≤ n donde n es el número de vértices ym son las aristas. Por lo tanto, la conversión de entrada se puede realizar en tiempo polinomial .

Conversión de salida: Necesitamos convertir la solución de Clique + IS a la solución del problema de Clique.

• La solución Clique+IS produce el conjunto C , que es un Clique de tamaño K , y el conjunto I , que es un conjunto independiente de tamaño K . 
• Esta solución se puede transformar en una solución del problema de Clique estableciendo C como un Clique de  tamaño K para el gráfico G.
• Eliminaremos los vértices I del conjunto independiente del gráfico G'(V’, E’) , lo que dará como resultado el gráfico G (V, E) , con Clique para G igual a Clique para G’ porque no hay diferencia de borde entre G y G’ .

Los vértices se pueden eliminar en O(n) ya que | yo | = K y K ≤ n donde n es el número de vértices, por lo que la conversión de salida se puede realizar en tiempo polinomial .

Corrección: ahora necesitamos probar la corrección de la afirmación que dice que la «Solución de Clique + IS existe si existe una solución al problema de Clique» .

• Creamos un nuevo gráfico G’= (V’, E’) a partir del gráfico G en el problema Clique, que contiene todos los vértices y aristas del gráfico G , así como los vértices del conjunto independiente I . 
• En comparación con el gráfico G , no se han añadido aristas adicionales en G’ . 
• Ahora bien, si existe una Clique C en el grafo G'(V’, E’) , también existirá en el grafo G(V, E) , porque la única diferencia entre G y G’ son los vértices del conjunto independiente I , que no están conectados por ningún borde y, por lo tanto, no serán parte del conjunto Clique C . 
• Esto demuestra que si Clique+IS tiene una solución, Clique también la tendrá, es decir, Clique+IS → Clique.

Además, como ambos gráficos tienen los mismos bordes, si no hay clique en el gráfico G'(V’, E’) , no puede existir clique en el gráfico G(V, E) . G’ tiene vértices adicionales del conjunto independiente I , pero no hay aristas que los conecten. Esto demostró que si Clique+IS no tiene solución, entonces Clique tampoco tiene solución, es decir, ! Clique-IS → ! Camarilla (¬Clique-IS → ¬Clique) . Esto demostró que Clique + IS existe si existe una solución al problema de Clique .

Conclusión:

Por lo tanto, podemos concluir que Clique+IS es un problema NP-completo.  

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