Problema del conjunto de cobertura

El problema del Set Covering, también conocido por sus siglas SCP es un problema clásico en combinatoria, ciencias de la computación y teoría de la complejidad computacional. Es un problema que ha llevado al desarrollo de técnicas fundamentales para el campo de los algoritmos de aproximación.^[1]​ También es uno de los problemas de la Lista de 21 problemas NP-completos de Karp cuya NP-completitud fue demostrada en 1972.

Dado un conjunto de elementos ${\displaystyle \{1,2,...,m\}}$ (llamado universo) y ${\displaystyle n}$ conjuntos cuya unión comprende el universo, el problema del conjunto de cobertura consiste en identificar el menor número de conjuntos cuya unión aun contiene todos los elementos del universo. Por ejemplo, sea ${\displaystyle U=\{1,2,3,4,5\}}$ y los conjuntos ${\displaystyle S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}}$. Claramente, la unión de todos los conjuntos de ${\displaystyle S}$ contiene todos los elementos de ${\displaystyle U}$. Sin embargo, podemos cubrir todos los elementos con el siguiente conjunto de elementos, con menor número de elementos: ${\displaystyle \{\{1,2,3\},\{4,5\}\}}$.

1. ↑ Vazirani (2001, p. 15)