# Covering by disjoint sets

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$.

I'm interested in the approximability of two problems, or in general, what is known about them.

1. Given a number $k'\in[m]$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$, $|\mathcal{S'}|=k'$ such that all of the sets in $\mathcal{S'}$ are disjoint.
2. Given a number $k''\in[n]$, is there a set $\mathcal{S''} \subseteq \mathcal{S}$ such that $|\cup_{s\in\mathcal{S''}}s|\geq k''$ (i.e. it covers at least $k$ elements) and the sets in $\mathcal{S''}$ are disjoint.

• The problems are NP-complete: The first has a straight forward reduction from 3-dimensional matching, and the second answers exact cover directly.
• The first problem seems $APX-hard$ if we use the hardness results from k-dimensional matching.
• Both problems can be viewed as a special case of Independent Set over the graph whose vertices are $\mathcal{S}$ and there's an edge $(s_i,s_j)$ iff $s_i\cap s_j$ isn't empty ( (2) has vertices weights $w(s_i)=|s_i|$), but I don't see any easy reduction from $IS$ to either that doesn't require exponential size blowup.

What can we say about the approximability of the two problems? maximal k-dimensional matching is known to be approximable within a factor of $\frac{k}{2}$, does it have an analogue for the first problem?

Both of these problems seems natural, so I'm tagging this question as a reference request, assuming they have been looked at under different name, rings a bell to anyone?

• There is an easy reduction from IS to Set Packing. For each vertex $v$ create a set $S_v$ which contains all the edges incident to $v$ as its elements. – Chandra Chekuri Mar 5 '14 at 21:44

1. Your first problem is more or less in-approximable. It contains "Independent Set" as a special case. For a graph $G=(V,E)$, define your ground set as $U:=V$ and for every vertex $v\in V$ construct a corresponding subset $S_v$ in your set system that contains the (closed) neighborhood of $v$. Then finding a cardinality-$k$ independent set in $G$ is equivalent to finding a cardinality-$k$ sub-system of disjoint sets in your set system. "Independent Set" cannot be approximated in polynomial time within a factor of $|V|^{1-\varepsilon}$ for any $\varepsilon>0$, unless P=NP.
Problem 1 is known as SET PACKING. Like other packing problems, it's annoyingly hard. The best known bound is a $O(\sqrt{|S|})$ approximation and it is indeed APX-hard.