Problema de la cobertura de vértices

Es muy utilizado en teoría de complejidad computacional para probar la pertenencia a la clase NP-hard de otros problemas computacionales difíciles.

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,

En este sentido, cada uno de estos problemas es dual al otro.

Este problema puede verse como un problema de decisión que pertenece a la clase de los NP-completos.

El problema permanece en NP-completo incluso en grafos cúbicos[1]​ y en grafos planares de grado mayor a 3.

[2]​ 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.