Minimum Cover

Input

Collection $C$ of subsets of a finite set $S$, positive integer $K \leq |C|$.

Question

Does $C$ contain a cover for $S$ of size $K$ or less, i.e. a subset $C' \subseteq C$ with $|C'| \leq K$ and such that very element of $S$ belongs to at least one member of $C'$?

Classes

• NP-complete

Comments

Remains NP-complete even if all $c \in C$ have $|c| \leq 3$. Solvable in polynomial time by matching techniques if all $c \in C$ have $|c| \leq 2$.

Proofs

NP-complete

Transformation from Exact Cover by 3-Sets (Karp, 1972).

Reducible from

• Exact Cover by 3-Sets

References

• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9