 Set cover problem

Given subsets $S_1,\dots ,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

The Set Cover Problem is a well-known problem in computer science and combinatorial optimization.