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