On the complexity of Compact Set r-Packing

The Set Packing problem is, given a collection of sets $S$ over a ground set $U$, to find maximum collection of sets that are pairwise disjoint. Since this problem is $NP$-hard, a natural restriction is to consider a parameterized version, Set r-Packing, which asks, given an additional parameter $r \in \mathbb{N}$, if there are $r$ sets in $S$ that are pairwise disjoint, with the hope that when $r$ is small, the problem becomes tractable. Unfortunately, Set r-Packing is not fixed parameter tractable; in fact it is complete for the class $W[1]$. Particularly, the intractability is known to occur when the universe size is at least linear in $|S|$. The algorithmic situation is further aggravated due to Exponential Time Hypothesis(ETH) which forbids $|S|^{o(r)}$ time algorithm for Set r-Packing.

In the quest for tractable instances, a natural motivation is to study the problem when the instances are "small". Towards this goal, equipped with the evidence of ETH, we consider Compact Set r-Packing problem, which restricts the instances of Set r-Packing to have small universe. Specifically, the instances of Compact Set r-Packing have $|U| = \widetilde{O}(f(r))$, for some function $f: f(r)\ge r$, where $\widetilde{O}(\cdot)$ hides polylog factors in $|S|$. In this direction, we show that Compact Set r-Packing remains fixed parameter intractable even when $f(r)=r$. On the other hand, we show a simple algorithm for Set Packing that runs in time $O^*(2^{|U|})$, where $O^*(\cdot)$ hides polynomial factors in $|S|$ and $|U|$, making Compact Set r-Packing fixed parameter tractable when $|U| = f(r)$. Both these results together characterize the transition(up to $\log$ factors) between tractable and intractable instances for Set r-Packing. As a corollary, our result provides an evidence that Compact Set r-Packing does not even admit $|S|^{o(\sqrt{r})}$ time algorithm. Finally, these results can be extended to the Exact r-Covering problem.