Prueba de que la cobertura de vértices es NP completa

Requisito previo: problema de cobertura de vértices , problema de NP-completitud
: dado un gráfico G (V, E) y un número entero positivo k, el problema es encontrar si hay un subconjunto V ‘de vértices de tamaño como máximo k, tal que cada borde en el gráfico está conectado a algún vértice en V’.

Explicación:
primero comprendamos la noción de una instancia de un problema. Una instancia de un problema no es más que una entrada al problema dado. Una instancia del problema de cobertura de vértices es un gráfico G (V, E) y un entero positivo k, y el problema es verificar si existe una cobertura de vértices de tamaño como máximo 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. Prueba de que la cobertura de vértices está en NP:
   si algún problema está en NP, entonces, dado un ‘certificado’ (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 para el problema de la cobertura de vértices es un subconjunto V’ de V, que contiene los vértices en la cobertura de vértices. Podemos verificar si el conjunto V’ es una cubierta de vértice de tamaño k usando la siguiente estrategia (para un grafo G(V, E)):

   let count be an integer
   set count to 0
   for each vertex v in V’
       remove all edges adjacent to v from set E
       increment count by 1
       if count = k and E is empty
       then
           the given solution is correct
       else
           the given solution is wrong
   

   Es fácil ver que esto se puede hacer en tiempo polinomial. Por tanto, el problema de la cobertura de vértices pertenece a la clase NP.

2. Prueba de que la cobertura de vértices es NP difícil:
   para demostrar que la cobertura de vértices es NP difícil, tomamos un problema que ya se ha demostrado que es NP difícil y mostramos que este problema se puede reducir al problema de la cobertura de vértices. Para esto, consideramos el problema Clique, que es NP Completo (y por lo tanto NP Difícil).
   

   “En informática, el problema de la camarilla es el problema computacional de encontrar camarillas (subconjuntos de vértices, todos adyacentes entre sí, también llamados subgrafos completos) en un gráfico”.

   Aquí, consideramos el problema de averiguar si hay una camarilla de tamaño k en el gráfico dado. Por lo tanto, una instancia del problema de la camarilla es un gráfico G (V, E) y un número entero no negativo k, y necesitamos verificar la existencia de una camarilla de
   tamaño k en G.

   Ahora, necesitamos mostrar que cualquier instancia (G, k) del problema Clique puede reducirse a una instancia del problema de cobertura de vértices. Considere el grafo G’ que consta de todas las aristas no en G, sino en el grafo completo usando todos los vértices en G. Llamemos a esto el complemento de G. Ahora, el problema de encontrar si existe una camarilla de tamaño k en el grafo G es lo mismo que el problema de encontrar si hay una cubierta de vértice de tamaño |V| – rey’. Tenemos que demostrar que esto es así.

   Suponga que hay una camarilla de tamaño k en G. Sea V’ el conjunto de vértices de la camarilla. Esto significa |V’| = k. En el grafo complementario G’, elijamos cualquier arista (u, v). Entonces al menos uno de uov debe estar en el conjunto V – V’. Esto se debe a que, si tanto u como v fueran del conjunto V’, entonces la arista (u, v) pertenecería a V’, lo que, a su vez, significaría que la arista (u, v) está en G. Esto es no es posible ya que (u, v) no está en G. Así, todas las aristas en G’ están cubiertas por vértices en el conjunto V – V’.

   Ahora suponga que hay una cubierta de vértice V» de tamaño |V| – rey’. Esto significa que todas las aristas en G’ están conectadas a algún vértice en V». Por tanto, si tomamos cualquier arista (u, v) de G’, ambas no pueden estar fuera del conjunto V». Esto significa que todas las
   aristas (u, v) tales que tanto u como v están fuera del conjunto V» están en G, es decir, estas aristas constituyen una camarilla de tamaño k.

Por lo tanto, podemos decir que hay una camarilla de tamaño k en el grafo G si y solo si hay una cubierta de vértice de tamaño |V| – k en G’ y, por lo tanto, cualquier instancia del problema de la camarilla se puede reducir a una instancia del problema de cobertura de vértices. Por lo tanto, la cobertura de vértices es NP Hard. Dado que la cobertura de vértices está en las clases NP y NP Hard, es NP Complete.

Para entender la prueba, considere el siguiente gráfico de ejemplo y su complemento:

Consulte para: prueba de que la ruta hamiltoniana es NP-completa