Half clique NP Problema completo

Una media camarilla en un gráfico es un conjunto de n/2 vértices tales que cada vértice comparte una arista con todos los demás vértices, es decir, los k = n/2 vértices del gráfico forman un gráfico completo. 

Problema – Dado un gráfico G(V,E), el problema es determinar si el gráfico contiene una camarilla de tamaño al menos k = |V/2|. 

Explicación 
: una instancia del problema es una entrada especificada para el problema. Una instancia del problema de Half-Clique es un gráfico G (V, E) y un entero positivo k, y el problema es verificar si una camarilla de tamaño k = |V/2| existe 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 Half-Clique está en 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), podremos 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 media 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 del gráfico G(V,E): 
 

flag=true
Count the number of vertices in the subset V' 
If not equal to V/2 :
    flag = false
Else : 
    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 la mitad de la camarilla es NP difícil:
para probar que el problema de la mitad de la camarilla 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 la mitad de la camarilla. Para esto, consideramos el problema Clique, que es NP Completo (y por lo tanto NP Difícil). 
Cada instancia del problema de 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’) y k’ del problema de camarilla medio. La deducción que se puede hacer es que el gráfico G’ tendrá una camarilla de tamaño n/2, si y sólo si el gráfico G tiene una camarilla de tamaño k. Sea m el número de Nodes en el grafo G. 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: