Set packing

Hypergraph matching is equivalent to set packing: the sets correspond to the hyperedges.

The independent set problem is also equivalent to set packing – there is a one-to-one polynomial-time reduction between them:

• Given a set packing problem on a collection ${\displaystyle {\mathcal {S}}}$, build a graph where for each set ${\displaystyle S\in {\mathcal {S}}}$ there is a vertex ${\displaystyle v_{S}}$, and there is an edge between ${\displaystyle v_{S}}$ and ${\displaystyle v_{T}}$ iff ${\displaystyle S\cap T\neq \varnothing }$. Every independent set of vertices in the generated graph corresponds to a set packing in ${\displaystyle {\mathcal {S}}}$.
• Given an independent vertex set problem on a graph ${\displaystyle G(V,E)}$, build a collection of sets where for each vertex ${\displaystyle v}$ there is a set ${\displaystyle S_{v}}$ containing all edges adjacent to ${\displaystyle v}$. Every set packing in the generated collection corresponds to an independent vertex set in ${\displaystyle G(V,E)}$.

This is also a bidirectional PTAS reduction, and it shows that the two problems are equally difficult to approximate.

In the special case when each set contains at most k elements (the k-set packing problem), the intersection graph is (k+1)-claw-free. This is because, if a set intersects some k+1 sets, then at least two of these sets intersect, so there cannot be a (k+1)-claw. So Maximum Independent Set in claw-free graphs[6] can be seen as a generalization of Maximum k-Set Packing.

Graph matching is a special case of set packing in which the size of all sets is 2 (the sets correspond to the edges). In this special case, a maximum-size matching can be found in polynomial time.

3-dimensional matching is a special case in which the size of all sets is 3, and in addition, the elements are partitioned into 3 colors and each set contains exactly one element of each color. This special case is still NP-hard, though it has better constant-factor approximation algorithms than the general case.

In the set cover problem, we are given a family ${\displaystyle {\mathcal {S}}}$ of subsets of a universe ${\displaystyle {\mathcal {U}}}$, and the goal is to determine whether we can choose t sets that together contain every element of ${\displaystyle {\mathcal {U}}}$. These sets may overlap. The optimization version finds the minimum number of such sets. The maximum set packing need not cover every possible element.

In the exact cover problem, every element of ${\displaystyle {\mathcal {U}}}$ should be contained in exactly one of the subsets. Finding such an exact cover is an NP-complete problem, even in the special case in which the size of all sets is 3 (this special case is called exact 3 cover or X3C). However, if we create a singleton set for each element of S and add these to the list, the resulting problem is about as easy as set packing.

Karp originally showed set packing NP-complete via a reduction from the clique problem.