Set Packing

Input

Collection $C$ of finite sets, positive integer $K \leq |C|$.

Question

Does $C$ contain at least $K$ mutually disjoint sets?

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