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

Assume $2\le k<m$ and ${\bigcup }_i{S}_i=S$. Construct a two-player game with row $i$ for $S_i$ and columns $0,1,\dots ,n$. Column $0$ pays both players one; column $j>0$ pays $(1,0)$ when $j\in S_i$, and $(0,k/(k-1))$ otherwise. There is a Nash equilibrium whose row player's support of a mixed strategy has size $k$ exactly when $k$ rows cover the universe. A uniform mixture on a cover makes column $0$ a best response. Conversely, if some element is uncovered by the support, the column player's best responses are uncovered elements and the row player's current payoff is zero. The union promise provides a profitable row deviation. Without the union promise the equivalence is false: a globally uncovered element is a best response against every row mixture.

// Target: mathematical-optimization.bigb