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.

Ejemplos de coberturas de vértices (conformadas por los vértices en rojo).

Ejemplos de coberturas de vértices mínimas.

Definición

 

La cobertura de vértices de un grafo no dirigido ${\displaystyle 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, ${\displaystyle \{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 ${\displaystyle \{2,4,5\}}$  y ${\displaystyle \{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 ${\displaystyle {\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^[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 32 (4): 826-834.  La referencia utiliza el parámetro obsoleto |coautores= (ayuda)

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

•   Datos: Q18222575