2
$\begingroup$
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})$)?
$\endgroup$
  • $\begingroup$ Take Set Packing with $n$ sets and ask for $k$ disjoint. It seems equivalent to Your Packing with $k$ collections, each containing same $n$ sets. $\endgroup$ – Karolis Juodelė Dec 8 '13 at 10:48
2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.