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).
In the set packing decision problem, the input is a pair
In the set packing optimization problem, the input is a pair
subsets, we can easily verify that they are pairwise disjoint in polynomial time.
The optimization version of the problem, maximum set packing, asks for the maximum number of pairwise disjoint sets in the list.
The maximum set packing problem can be formulated as the following integer linear program.
When k=2, the problem is equivalent to finding a maximum cardinality matching, which can be solved in polynomial time.
However, there are constant-factor approximation algorithms: In another more tractable variant, if no element occurs in more than d of the subsets, the answer can be approximated within a factor of d. This is also true for the weighted version.
The independent set problem is also equivalent to set packing – there is a one-to-one polynomial-time reduction between them: 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.
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.
, and the goal is to determine whether we can choose t sets that together contain every element of
The optimization version finds the minimum number of such sets.
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).
Karp originally showed set packing NP-complete via a reduction from the clique problem.