If you want to make money online : Register now

[Solved]: Set packing variant

, , No Comments
Problem Detail: 
There are n collections of M sets. Pick a single set from each collection, such that all n picked sets are pairwise disjoint. 

This problem can be converted to the standard Set Packing problem in the following way: add a unique element $e_i$ to all $M$ sets in each collection $C_i$. Then find a set packing of size $n$ in the resulting collection. Each set in the returned set packing must belong to a different collection.

So, the variant is not more difficult than the original set packing problem.

MY QUESTION IS: is the variant easier than the original problem? In particular:

  • Is it possible to solve the variant problem in time polynomial in $n$ (assuming $M$ is constant)?
  • Is it possible to approximate the variant problem in a more efficient way than the approximations known for the general set packing problem (i.e. $O(\sqrt{nM})$)?
Asked By : Erel Segal-Halevi

Answered By : Luke Mathieson

Let $(U,S,k)$ be an instance of Set Packing where $U$ is base set, $S$ is the collection of sets over $U$ and $k$ is the minimum size of the desired set packing.

We can construct an instance of Erel's Set Packing (nice name, no? ;) ) by taking $k$ copies of $S$ (i.e. $n=k$, $M=|S|$), label them $S_{i}$ for $1\leq i\leq k$.

Then if $(U,S,k)$ has a set packing of size at least $k$, there is some set $C \subseteq S$ such that $|C| \geq k$ and for every pair $c_{i},c_{j} \in C$, we have $c_{i} \cap c_{j} = \emptyset$. Moreover, this also holds for every $k$ sized subset of $C$. Arbitrarily pick one of these $k$ sized subsets $C' = \{c_{1},\ldots,c_{k}\}$, this will correspond to a solution for Erel's Set Packing where we take (in whatever order you care for) $c_{i}$ in $S_{i}$.

The reverse is also (clearly) true, a solution for Erel's Set Packing consists of $k$ pairwise disjoint sets, one from each $S_{i}$, but as all the $S_{i}$s are just copies of each other, all the sets they correspond to sets from the original $S$ that are pairwise disjoint.

So then the variant problem is also NP-complete, though I'm not sure what happens when $M=c$ for some constant $c$, I suspect it remains hard though (from just an intuition standpoint, no firm evidence).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18737

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback