Problema de la cobertura de vértices
# Problema de la cobertura de vértices

En ciencias de la computación, el Problema de la cobertura 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-hard de otros problemas computacionales difíciles.

## Definición

La cobertura de vértices de un grafo no dirigido $G=(V,E)$ es un subconjunto S de V (el conjunto de vértices) tal que para cada arista ab del conjunto E, ya sea el vértice a o b pertenece a S.

Ejemplo: En el grafo de la derecha, $\{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 ${\bar {S}}=V\setminus S$ es un conjunto independiente. Así, un grafo con n vértices tiene una cobertura de vértices de tamaño k si 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.

## Tratabilidad

Este problema puede verse como un problema de decisión que pertenece a la clase de los NP-completos. Esto porque existen otros conocidos problemas NP-completos, como el problema SAT o el Problema de la clique que pueden ser polinomialmente reducidos a él. El problema permanece en NP-completo incluso en grafos cúbicos y en grafos planares de grado mayor a 3.

Para grafos bipartitos, existe una equivalencia entre el problema de cobertura de vértices y el problema del matching máximo, descrito en el Teorema de König, que permite una resolución del problema en tiempo polinomial.

