## 3.5.1 ALGORITMO DE APROXIMACIÓN PARA EL PROBLEMA DE LA CUBIERTA DE VÉRTICES

El Problema de la cubierta de vértices es un problema NP-completo, que pertenece a los 21 problemas NP-completos de Karp. Es muy utilizado en teoría de complejidad computacional para probar la pertenencia a la clase NP-duros de otros problemas computacionales difíciles.

Una cobertura de un grafo no dirigido G = ( V, A ) es un subconjunto V´ ⊆ V tal que si ( u, v ) ∈ A, entonces u ∈ V´ o v ∈ V´ (o ambos).

Cada vértice “cubre” sus aristas incidentes, y una cobertura es un conjunto de vértices que cubre todas las aristas. El tamaño de una cobertura es el número de vértices.

El Problema de la Cobertura de vértices consiste en encontrar una cobertura de tamaño mínimo.

El Problema de Decisión de la Cobertura de Vértices consiste en determinar si un grafo tiene una cobertura de tamaño como mucho k.

Ejemplo:

En el grafo, {1,3,5,6} es una cobertura de vértices de tamaño 4. Sin embargo, esta no es la cobertura mínima, porque existen las coberturas de vértices {2,4,5} y {1,2,4}, ambas de tamaño 3.

El Problema de cobertura de vértices es un problema de optimización que consiste en encontrar una cobertura de vértices de tamaño k en un grafo dado.

  ENTRADA: Grafo G.
  SALIDA: El menor número k tal que exista una cobertura de vértices S para G de tamaño k.

Equivalentemente, el problema puede definirse como un problema de decisión:

  ENTRADA: Grafo G y un entero positivo k.
  PREGUNTA: ¿Existe una cobertura de vértices S para G de tamaño menor o igual a k?

La cobertura de vértices está estrechamente relacionada con el Problema del conjunto independiente. Un conjunto de vértices S es una cobertura de vértices si y sólo si su complemento {SC= V\S} es un conjunto independiente. Así, un grafo con n vértices tiene una cobertura de vértices de tamaño ksi y sólo si el grafo tiene un conjunto independiente de tamaño n-k. En este sentido, cada uno de estos problemas es dual al otro.

###