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 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 puedes ser polinomialmente reducidos a él. 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.

Véase también

• Cobertura de vértices
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.1: GT1, pg.190.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 35.1, pp.1024–1027.

Referencias

1. ↑ Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), «Some simplified NP-complete problems», Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 47-63 
2. ↑ Garey, M. R.; D. S. Johnson (1977). «The rectilinear Steiner tree problem is NP-complete» SIAM Journal on Applied Mathematics. Vol. 32. n.º 4. pp. 826-834.

Enlaces externos

• Un compendio de problemas NP de optimización
• Benchmarks de desafío para Clique máximo, Conjunto independiente máximo, Cobertura de vértices mínima y Coloración de grafos