# Set packing variant

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})$)?
• 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. – Karolis Juodelė Dec 8 '13 at 10:48

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