Prueba de que el problema de decisión de camarilla es NP-Completo

Requisito previo: NP-Completitud

Una camarilla es un subgrafo de un grafo tal que todos los vértices en este subgrafo están conectados entre sí, es decir, el subgrafo es un grafo completo. El problema de la camarilla máxima es encontrar la camarilla de tamaño máximo de un gráfico G dado, que es un gráfico completo que es un subgráfico de G y contiene el número máximo de vértices. Este es un problema de optimización. En consecuencia, el problema de decisión de camarilla es encontrar si una camarilla de tamaño k existe en el gráfico dado o no. 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 decisión de Clique pertenece a NP : si un problema pertenece a la clase NP, entonces debería tener verificabilidad en tiempo polinomial, es decir, se le otorga un certificado, deberíamos poder verificar en tiempo polinomial si es una solución al problema.

Prueba:

1. Certificado : sea el certificado un conjunto S que consta de Nodes en la camarilla y S es un subgrafo de G.
2. Verificación : tenemos que verificar si existe una camarilla de tamaño k en el gráfico. Por lo tanto, verificar si el número de Nodes en S es igual a k toma O(1) tiempo. Verificar si cada vértice tiene un grado de salida de (k-1) lleva O(k ² ) tiempo. (Dado que en un gráfico completo, cada vértice está conectado a todos los demás vértices a través de una arista. Por lo tanto, el número total de aristas en un gráfico completo = ^k C ₂ = k*(k-1)/2 ). Por tanto, para comprobar si el grafo formado por los k Nodes en S está completo o no, se necesita un tiempo O(k ² ) = O(n ² ) (ya que k<=n, donde n es el número de vértices en G).

Por lo tanto, el problema de decisión de camarilla tiene verificabilidad en tiempo polinomial y, por lo tanto, pertenece a la clase NP.

El problema de decisión de Clique pertenece a NP-Hard : un problema L pertenece a NP-Hard si cada problema NP es reducible a L en tiempo polinomial. Ahora, dejemos el problema de decisión de Clique por C. Para probar que C es NP-Difícil, tomamos un problema NP-Difícil ya conocido, digamos S, y lo reducimos a C para una instancia particular. Si esta reducción se puede hacer en tiempo polinomial, entonces C también es un problema NP-Difícil. El Problema de Satisfacción Booleano (S) es un problema NP-Completo como lo demuestra el teorema de Cook . Por lo tanto, todo problema en NP se puede reducir a S en tiempo polinomial. Por lo tanto, si S es reducible a C en tiempo polinomial, todo problema NP puede reducirse a C en tiempo polinomial, demostrando así que C es NP-Difícil.

Demostración de que el problema de Satisfacción Booleano se reduce al Problema de Decisión de Clique
Sea la expresión booleana – F = (x ₁ vx ₂ ) ^ (x ₁ ‘ vx ₂ ‘) ^ (x ₁ vx ₃ ) donde x ₁ , x ₂ , x ₃ son las variables, ‘^’ denota ‘y’ lógico, ‘v’ denota ‘o’ lógico y x’ denota el complemento de x. Deje que la expresión dentro de cada paréntesis sea una cláusula. Por lo tanto, tenemos tres cláusulas: C ₁ , C ₂ y C ₃ . Considere los vértices como – <x ₁ , 1>; <x2 , ₁ >; <x ₁ ‘, 2>; <x₂ ‘, 2>; <x1 , ₃ >; <x ₃ , 3> donde el segundo término de cada vértice denota el número de cláusula al que pertenecen. Conectamos estos vértices de tal manera que:

1. No hay dos vértices que pertenezcan a la misma cláusula conectados.
2. Ninguna variable está conectada a su complemento.

Así, el grafo G (V, E) se construye de manera que – V = { <a, i> | a pertenece a C _i } y E = { ( <a, i>, <b, j> ) | i no es igual a j ; b no es igual a a’ } Considere el subgrafo de G con los vértices <x ₂ , 1>; <x ₁ ‘, 2>; <x ₃ , 3>. Forma una camarilla de tamaño 3 (representada por la línea de puntos en la figura anterior). Correspondiente a esto, para la tarea – <x ₁ , x ₂ , x ₃> = <0, 1, 1> F se evalúa como verdadero. Por lo tanto, si tenemos k cláusulas en nuestra expresión de satisfacibilidad, obtenemos una camarilla máxima de tamaño k y para la asignación de valores correspondiente, la expresión de satisfacibilidad se evalúa como verdadera. Por lo tanto, para un caso particular, el problema de satisfacibilidad se reduce al problema de decisión de la camarilla. 

Por lo tanto, el problema de decisión de la camarilla es NP-difícil.

Conclusión
El problema de decisión de la camarilla es NP y NP-Hard. Por lo tanto, el problema de decisión de Clique es NP-Completo.

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