# Algorithms for set packing

There seems to be much work, for some NP-Hard problems, on developing fast exponential time exact algorithms (i.e., results of the form: Algorithm A solves problem $x$ in O(c^n) time, with c small). There seems to be a fair amount of work along these lines for some NP-hard problems (e.g., Measure and conquer: a simple $O(2^{0.288n})$ independent set algorithm. SODA’06) but I haven't been able to find similar work for the set packing problem. There seems to be similar work on some restrictions of the set packing problem (e.g., An $O^{*}(3.523^{k})$ Parameterized Algorithm for 3-Set Packing) but I haven't found any for the general set packing problem.

So my question is: What is the best time complexity for exactly solving the weighted set packing problem where there are $m$ sets drawn from a universe of $n$ elements?

I am also interested in the relationship between the number of sets and the size of the universe. For example, has there been algorithmic work on situations where $m$ is relatively large compared to $n$ (i.e., close to $2^n$)?

• Google ? "set packing" ? en.wikipedia.org/wiki/Set_packing this is not a research level question yet (see our FAQ). Closing now... – Suresh Venkat Dec 25 '10 at 5:07
• @Suresh, I am interested in results of the form: Algorithm A solves the set packing problem in O(c^n) time, with c small. There is such work for other NP-hard problems (e.g., Measure and conquer: a simple O(2^0.288n) independent set algorithm. SODA’06). The wikipedia article you link doesn't discuss this and I have not found any recent articles discussing set packing's time complexity. Most work I have found is on the k-set packing problem. This is a "request-for-reference" type question. Are these sort of questions welcome here? or perhaps the question was not written well enough? – Travis Service Dec 25 '10 at 16:36
• That makes a lot more sense actually. the key point is that you are looking for EXACT algorithms for weighted set packing. If you'd like to reword, provide any references for $k$-set packing (as well as what it is), then I'd be happy to reopen - just flag it for moderator attention. – Suresh Venkat Dec 25 '10 at 17:53
• I'd advocate reopening this question. "Time complexity" usually refers to exact algorithms, unless stated otherwise, no? – arnab Dec 27 '10 at 5:12
• This question should be reopened. – Peter Shor Dec 30 '10 at 2:25

Indeed, set packing, partitioning, and covering have been studied in terms of exact algorithm running times. To address your last question, you can solve weighted set packing in $O(m2^n)$ time by dynamic programming across all subsets of $[n]$. Moreover, if your integer weights are bounded by $M$, you can solve it in $O(M2^n)$ time, even if $m$ is as large as $2^n$, see
BTW, The parameterized result you list for $3$-sets is not the best known, see
You mention Measure and conquer: a simple $O(2^{0.288n})$ independent set algorithm. SODA’06. There seems to be a one-to-one polynomial-time reduction between independent-set and set-packing. Therefore, the results for the independent set problem should be applicable to set packing as well.