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 ${\mathcal {U}}$ and a family ${\mathcal {S}}$ of subsets of ${\mathcal {U}}$ , a packing is a subfamily ${\mathcal {C}}\subseteq {\mathcal {S}}$ of sets such that all sets in ${\mathcal {C}}$ are pairwise disjoint. The size of the packing is $|{\mathcal {C}}|$ . In the set packing decision problem, the input is a pair $({\mathcal {U}},{\mathcal {S}})$ and an integer $t$ ; the question is whether there is a set packing of size $t$ or more. In the set packing optimization problem, the input is a pair $({\mathcal {U}},{\mathcal {S}})$ , and the task is to find a set packing that uses the most sets.

The problem is clearly in NP since, given $t$ 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. It is a maximization problem that can be formulated naturally as an integer linear program, belonging to the class of packing problems.

Integer linear program formulation

The maximum set packing problem can be formulated as the following integer linear program.

maximize	$\sum _{S\in {\mathcal {S}}}x_{S}$		(maximize the total number of subsets)
subject to	$\sum _{S\colon e\in S}x_{S}\leqslant 1$	for all $e\in {\mathcal {U}}$	(selected sets have to be pairwise disjoint)
	$x_{S}\in \{0,1\}$	for all $S\in {\mathcal {S}}$ .	(every set is either in the set packing or not)

Complexity

The set packing problem is not only NP-complete, but its optimization version (general maximum set packing problem) has been proven as difficult to approximate as the maximum clique problem; in particular, it cannot be approximated within any constant factor.^[1] The best known algorithm approximates it within a factor of $O({\sqrt {|{\mathcal {U}}|}})$ .^[2] The weighted variant can also be approximated as well.^[3]

Packing sets with a bounded size

The problem does have a variant which is more tractable. Given any positive integer k≥3, the k-set packing problem is a variant of set packing in which each set contains at most k elements.

When k=1, the problem is trivial. When k=2, the problem is equivalent to finding a maximum cardinality matching, which can be solved in polynomial time.

For any k≥3, the problem is NP-hard, as it is more general than 3-dimensional matching. However, there are constant-factor approximation algorithms:

Cygan^[4] presented an algorithm that, for any ε>0, attains a (k+1+ε)/3 approximation. The run-time is polynomial in the number of sets and elements, but doubly-exponential in 1/ε.
Furer and Yu^[5] presented an algorithm that attains the same approximation, but with run-time singly-exponential in 1/ε.

Packing sets with a bounded degree

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.