Hitting Set

Input

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

Question

Is there a subset $S' \subseteq S$ with $|S'| \leq K$ such that $S'$ contains at least one element from each subset in $C$?

Classes

• NP-complete

Comments

Remains NP-complete even if $|c| \leq 2$ for all $c \in C$.

Proofs

NP-complete

Transformation from Vertex Cover (Karp, 1972).

Reducible from

• Vertex Cover

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