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.{{citation

| last1 = Hazan | first1 = Elad

| last2 = Safra | first2 = Shmuel

| last3 = Schwartz | first3 = Oded

| doi = 10.1007/s00037-006-0205-6

| issue = 1

| journal = Computational Complexity

| mr = 2226068

| pages = 20–39

| title = On the complexity of approximating k-set packing

| volume = 15

| year = 2006| citeseerx = 10.1.1.352.5754

| s2cid = 1858087

}}. See in particular p. 21: "Maximum clique (and therefore also maximum independent set and maximum set packing) cannot be approximated to within $O(n^{1-\epsilon})$ unless NP ⊂ ZPP." The best known algorithm approximates it within a factor of $O(\sqrt$

\mathcal{U}

).{{cite conference

| last1 = Halldórsson | first1 = Magnus M.

| last2 = Kratochvíl | first2 = Jan

| last3 = Telle | first3 = Jan Arne

| title = Independent sets with domination constraints

| conference = 25th International Colloquium on Automata, Languages and Programming

| series = Lecture Notes in Computer Science

| volume = 1443

| publisher = Springer-Verlag

| pages = 176–185

| year = 1998

}} The weighted variant can also be approximated as well.{{cite conference

| last = Halldórsson | first = Magnus M.

| year = 1999

| title = Approximations of weighted independent set and hereditary subset problems

| conference = 5th Annual International Conference on Computing and Combinatorics

| series = Lecture Notes in Computer Science

| volume = 1627

| publisher = Springer-Verlag

| pages = 261–270

}}

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{{Cite book |last=Cygan |first=Marek |title=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |chapter=Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search |date=October 2013 |chapter-url=https://ieeexplore.ieee.org/document/6686187 |pages=509–518 |doi=10.1109/FOCS.2013.61|arxiv=1304.1424 |isbn=978-0-7695-5135-7 |s2cid=14160646 }} 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{{Cite conference |last1=Fürer |first1=Martin |last2=Yu |first2=Huiwen |title=Combinatorial Optimization |chapter=Approximating the {{mvar|k}}-set packing problem by local improvements |date=2014 |editor-last=Fouilhoux |editor-first=Pierre |editor2-last=Gouveia |editor2-first=Luis Eduardo Neves |editor3-last=Mahjoub |editor3-first=A. Ridha |editor4-last=Paschos |editor4-first=Vangelis T. |chapter-url=https://link.springer.com/chapter/10.1007/978-3-319-09174-7_35 |series=Lecture Notes in Computer Science |volume=8596 |language=en |location=Cham |publisher=Springer International Publishing |pages=408–420 |doi=10.1007/978-3-319-09174-7_35 |isbn=978-3-319-09174-7|s2cid=15815885 }} 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.

= Equivalent problems =

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 $\mathcal{S}$ , build a graph where for each set $S \in \mathcal{S}$ there is a vertex $v_S$ , and there is an edge between $v_S$ and $v_T$ iff $S \cap T \neq \varnothing$ . Every independent set of vertices in the generated graph corresponds to a set packing in $\mathcal{S}$ .
Given an independent vertex set problem on a graph $G(V,E)$ , build a collection of sets where for each vertex $v$ there is a set $S_v$ containing all edges adjacent to $v$ . Every set packing in the generated collection corresponds to an independent vertex set in $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{{cite conference

| last = Neuwohner | first = Meike

| editor1-last = Bläser | editor1-first = Markus

| editor2-last = Monmege | editor2-first = Benjamin

| arxiv = 2106.03545

| contribution = An improved approximation algorithm for the maximum weight independent set problem in {{mvar|d}}-claw free graphs

| doi = 10.4230/LIPICS.STACS.2021.53

| pages = 53:1–53:20

| publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik

| series = LIPIcs

| title = 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16–19, 2021, Saarbrücken, Germany (Virtual Conference)

| volume = 187

| year = 2021| doi-access = free

}} can be seen as a generalization of Maximum k-Set Packing.

= Special cases =

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.

Notes

References

"[https://xlinux.nist.gov/dads/HTML/setpacking.html set packing]". Dictionary of Algorithms and Data Structures, editor Paul E. Black, National Institute of Standards and Technology. Note that the definition here is somewhat different.
Steven S. Skiena. "[http://www3.cs.stonybrook.edu/~algorith/files/set-packing.shtml Set Packing]". The Algorithm Design Manual.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger. "[https://www.csc.kth.se/~viggo/wwwcompendium/node144.html Maximum Set Packing]". [https://www.csc.kth.se/%7Eviggo/wwwcompendium/ A compendium of NP optimization problems]. Last modified March 20, 2000.
{{cite book|author = Michael R. Garey and David S. Johnson | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 978-0-7167-1045-5| title-link = Computers and Intractability: A Guide to the Theory of NP-Completeness }} A3.1: SP3, pg.221.
{{Cite book | last=Vazirani | first=Vijay V. | author-link=Vijay Vazirani | title=Approximation Algorithms | year=2001 | publisher=Springer-Verlag | isbn=978-3-540-65367-7 }}

External links

[http://www.cs.sunysb.edu/~algorith/implement/syslo/implement.shtml]: A Pascal program for solving the problem. From Discrete Optimization Algorithms with Pascal Programs by MacIej M. Syslo, {{isbn|0-13-215509-5}}.
[http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/set-benchmarks.htm Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination]
[https://web.archive.org/web/20101226041147/http://www.phpqa.in/2010/10/solving-packaging-problem-in-php.html Solving packaging problem in PHP]
[https://web.archive.org/web/20190303205438/http://pdfs.semanticscholar.org/bb99/86af2f26f7726fcef1bc684eac8239c9b853.pdf Optimizing Three-Dimensional Bin Packing]

Category:Combinatorics

Category:NP-complete problems