Prueba de que el conjunto dominante de un gráfico es NP-completo

Prerrequisito: Conjunto Dominante de un Gráfico , NP-Completo

Un conjunto dominante en un grafo G = (V, E) es un subconjunto de vértices V’ siguiendo la condición de que los vértices que no pertenecen a V’ sean adyacentes a algún vértice en V’ .

Problema: Dado un grafo G(V, E) y un entero k, el problema es determinar si el grafo tiene un Conjunto Dominante de tamaño k.
Explicación:
una instancia del problema es una entrada especificada para el problema. Una instancia del problema del Conjunto Dominante es una gráfica G (V, E) y un entero k, y el problema es verificar si la gráfica puede tener un conjunto dominante 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 conjunto dominante es NP completo
   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), haremos poder verificar (comprobar si la solución dada es correcta o no) el certificado en tiempo polinomial.
   El certificado es una secuencia de vértices que forman un Conjunto Dominante en el grafo. Podemos validar esta solución comprobando que todos los vértices pertenecen a los vértices del gráfico y que todos los vértices que no forman parte de esta secuencia son adyacentes a algunos de los vértices de este conjunto. Esto se puede hacer en tiempo polinomial, es decir O(V +E) usando la siguiente estrategia:

   flag=true
   for every vertex v in V:
     if v doesn't belong to Dominating Set:
        verify the set of edges 
        corresponding to v 
        if v is not adjacent 
           to any of the vertices in DS, 
           set flag=False and break
   if (flag)
      solution is correct
   else
      solution is incorrect
   

2. El Conjunto Dominante es NP-Difícil
   Para demostrar que el Conjunto Dominante es NP-Difícil, tendremos que reducir un problema NP-Difícil conocido a este problema. Realizaremos una reducción del problema de la Cobertura de Vértices al problema del Conjunto Dominante.
   Cada instancia del problema de cobertura de vértices consiste en un gráfico G = (V, E) y un número entero k que consiste en el subconjunto de vértices como entrada se puede convertir en un problema de conjunto dominante que consiste en el gráfico G’ = (V’, E ‘) . Construiremos el grafo G’ de la siguiente forma:
   • E’ = Para cada arista E que consta de vértices {u, v} en el grafo G, agrega un nuevo vértice {uv} y únelo individualmente a los nuevos vértices u y v.
   • V’ = Sumar todos los vértices V del grafo original G.

   El nuevo grafo G’ se puede obtener en tiempo polinomial, añadiendo nuevas aristas correspondientes al nuevo vértice, que requiere tiempo O(V+E) . Esta reducción puede probarse mediante las dos afirmaciones siguientes:

   • Supongamos que el grafo G tiene una cubierta de vértice VC de tamaño k. Cada arista en G tiene uno de los vértices perteneciente a la cubierta de vértices. Por lo tanto, para cada borde e, que consta de vértices {u, v}, al menos u o v es parte de la cubierta de vértice. Entonces, si u está contenido en VC, entonces el vértice adyacente es v, también está cubierto por algunos de los elementos en VC. Ahora, para todos los vértices UV recién agregados para cada borde, el vértice es adyacente tanto a u como a v, uno de los cuales es al menos una parte del VC, como se demostró anteriormente. Por lo tanto, los vértices adicionales para todas las aristas también están cubiertos por este VC. El conjunto de vértices que forman la Cobertura de Vértices de tamaño k forman el Conjunto Dominante en el grafo G’. Por lo tanto, si G tiene una cubierta de vértice, G’ tiene un conjunto dominante del mismo tamaño.
   • Suponemos que el grafo G’ tiene un Conjunto Dominante de tamaño k. Pueden surgir dos posibilidades, o el vértice en el DS es un vértice original o pertenece al vértice UV recién agregado para cada borde {u, v}. En el segundo caso, dado que cada nuevo vértice está conectado a los dos vértices de la arista, u y v, por lo tanto, puede ser reemplazado por u o v. Dado que estos tres vértices forman un triángulo, por lo tanto, incluso reemplazando vista con u o v, podemos continuar expandiendo todos los vértices que se expandieron antes de reemplazar. Esto conducirá a la eliminación de todos los vértices recién agregados mientras se expanden todos los bordes del gráfico G’. Los vértices recién agregados están dominados por el DS modificado y cubren todos los bordes en G con al menos u o v para cada borde UV. Por tanto, si G’ tiene un Conjunto Dominante de tamaño k,

En la siguiente figura, el vértice B domina tanto AB como BE, por lo tanto, se puede reemplazar fácilmente. Por lo tanto, estos dos vértices son redundantes.

Así podemos decir que el grafo G’ contiene un conjunto dominante si y sólo si el grafo G contiene cobertura de vértices. Por lo tanto, cualquier instancia del problema del conjunto dominante puede reducirse a una instancia del problema de cobertura de vértices. Por lo tanto, el conjunto dominante también es NP-Hard. Dado que la cobertura de vértices está en las clases NP y NP-Hard, el Conjunto dominante de un gráfico es NP-Completo.