Set packing

Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.

Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint (in other words, no two of them share an element).

More formally, given a universe ${\displaystyle {\mathcal {U}}}$ and a family ${\displaystyle {\mathcal {S}}}$ of subsets of ${\displaystyle {\mathcal {U}}}$, a packing is a subfamily ${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$ of sets such that all sets in ${\displaystyle {\mathcal {C}}}$ are pairwise disjoint, and the size of the packing is ${\displaystyle |{\mathcal {C}}|}$. In the set packing decision problem, the input is a pair ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$ and an integer ${\displaystyle k}$; the question is whether there is a set packing of size ${\displaystyle k}$ or more. In the set packing optimization problem, the input is a pair ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$, and the task is to find a set packing that uses the most sets.

...
Wikipedia