Problema de la cobertura de vértices

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.

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.

• 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.

• 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