1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Mar 5 '14 at 21:44
1
$\begingroup$
  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.

  2. Your second problem is known as "Maximum k-Coverage". It is APX-complete (and hence does not allow a PTAS), but has a (poly-time) constant factor approximation algorithm due to Hochbaum and Pathria:

Hochbaum, D. S. and Pathria, A. (1998), Analysis of the greedy approach in problems of maximum k-coverage. Naval Research Logistics 45: 615–627.

link to Hochbaum & Pathria paper

$\endgroup$
1
$\begingroup$

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.

$\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.