Problema de cobertura (combinatoria)

En combinatoria y ciencias de la computación, los problemas de cobertura son problemas computacionales que preguntan si una determinada estructura combinatoria 'cubre' a otra, o qué tan grande debe ser la estructura para hacer eso. Los problemas de cobertura son problemas de minimización y, por lo general, programas lineales, cuyos problemas duales se denominan problemas de empaque.

Los ejemplos más destacados de problemas de cobertura son el problema de cobertura de conjuntos, que es equivalente al problema de acierto de conjuntos, y sus casos especiales, el problema de cobertura de vértices y el problema de cobertura de bordes.

Formulación de programación lineal general 
En el contexto de la programación lineal, se puede pensar en cualquier programa lineal como un problema de cobertura si los coeficientes de la matriz de restricción, la función objetivo y el lado derecho no son negativos. Más precisamente, considere el siguiente programa lineal de enteros general:

Tal programa lineal de enteros se llama problema de cobertura si  para todo  y .

Intuición: suponga tener  tipos de objeto y cada objeto de tipo  tiene un costo asociado de . El número  indica cuántos objetos de tipo  compramos. Si las restricciones  están satisfechos, se dice que  es una cobertura (las estructuras que se cubren dependen del contexto combinatorio). Finalmente, una solución óptima para el programa lineal de enteros anterior es una cobertura de costo mínimo.

Tipos de problemas de cobertura 
Hay varios tipos de problemas de cobertura en teoría de grafos, geometría computacional y más.

En el caso de las redes de Petri, por ejemplo, el problema de la cobertura se define como la cuestión de si para una marca determinada existe un recorrido de la red, de modo que se pueda alcanzar una marca mayor (o igual). Más grande significa aquí que todos los componentes son al menos tan grandes como los de la marca dada y al menos uno es adecuadamente más grande.

Cobertura de arcoíris y cobertura libre de conflictos 
En algunos problemas de cobertura, la cobertura debería satisfacer algunos requisitos adicionales. En particular, en el problema de la cubierta del arco iris, cada uno de los objetos originales tiene un "color", y se requiere que la cubierta contenga exactamente un (o como mucho uno) objeto de cada color. Se estudió la cobertura del arco iris, por ejemplo, para cubrir puntos por intervalos:

 Hay un conjunto J de n intervalos de colores en la línea real y un conjunto P de puntos en la línea real.
 Un subconjunto Q de J se denomina conjunto de arco iris si contiene como máximo un intervalo único de cada color.
 Un conjunto de intervalos de J se llama un recubrimiento de P si cada punto en P está contenida en al menos un intervalo de Q.
 El problema que cubre arco iris es el problema de encontrar un conjunto de arco iris Q que es una cubierta de P.

El problema es NP-duro (por reducción de SAT lineal).

Una noción más general es cobertura libre de conflictos. En este problema:

 Hay un conjunto O de m objetos, y un conflicto-gráfico GO en O.
 Un subconjunto Q de O se llama libre de conflictos si es un conjunto independiente en GO, es decir, no hay dos objetos en Q están conectadas por un borde en GO.
 Un conjunto de arcoíris es un conjunto libre de conflictos en el caso especial en el que GO está formado por grupos separados, donde cada grupo representa un color.

El problema de la cobertura de conjunto libre de conflictos es el problema de encontrar un subconjunto libre de conflictos de O que es una cubierta de P. Banik, Panolan, Raman, Sahlot y Saurabh  prueban lo siguiente para el caso especial en el que el gráfico de conflicto tiene arboricidad limitada:

 Si el problema de la cubierta geométrica es tratable con parámetros fijos (FPT), entonces el problema de la cubierta geométrica libre de conflictos es FPT.
 Si el problema de cobertura geométrica admite un algoritmo de aproximación r, entonces el problema de cobertura geométrica libre de conflicto admite un algoritmo de aproximación similar en tiempo FPT.

Véase también 
 Apareamiento (teoría de grafos)
 Cobertura de aristas
 Cobertura de vértices
 Conjunto independiente
 Problema del conjunto de cobertura
 Set packing

Referencias
 

Optimización
Combinatoria
Problemas matemáticos