La cobertura de vértices de un grafo no dirigido es un subconjuntoS de V (el conjunto de vértices) tal que para cada aristaab del conjunto E, ya sea el vértice a o b pertenece a S.
Ejemplo: En el grafo de la derecha, 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 y , 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.
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 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.
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.
