Set cover problem
= Set cover problem
{wiki}
= Subset cover problem
{synonym}
Given subsets $S_1,\ldots,S_m$ of a finite universe, the decision problem asks whether at most $k$ of them cover the universe. It is <NP-complete>. If $k<m$, existence of a cover by at most $k$ subsets is equivalent to existence of a cover by exactly $k$, by adding unused subsets. The promise that every element occurs in some subset loses no hardness: an uncovered element can be detected in polynomial time and mapped to a fixed negative instance.
// Target: mathematical-optimization.bigb