6
$\begingroup$

The Minimum Cardinality Exact Cover (MCEC) problem is just like set cover, but the output sets must be disjoint.

Formally, given a collection of subsets $S$ of a finite set $U$, the problem asks for a subcollection $S'$ of $S$ of minimum cardinality such that the union of $S'$ is $U$, and $S_1 \cap S_2 = \emptyset$ for every distinct $S_1, S_2 \in S'$.

We may assume that for each $u \in U$' there is a set $S_u = \{u\}$ in $S$. This ensures that there exists an exact cover of cardinality at most $|U|$.

I'd like to know if MCEC is as hard to approximate as set cover, i.e. cannot be approximated to within a $\log |U|$ factor. I can show that MCEC has no constant factor approximation, reducing from $k$-Set-Cover for any constant $k$ by adding every subset of a set present in the set cover input. But having the same inapproximability as set cover would be stronger.

$\endgroup$
  • $\begingroup$ Exact Cover (deciding whether such an $S'$ exists, ignoring cardinality constraints) is NP-hard wikipedia. Are you considering the case where you promise that an exact cover exists, and want to find the smallest one? $\endgroup$ – user53923 Jul 26 '18 at 9:09
  • $\begingroup$ Ah yes you're right, I forgot about that - there can't be any approximation without some kind of promise. We may assume that $S$ has a set $S_u = \{u\}$ for each $u \in U$. I edited the question. $\endgroup$ – Manuel Lafond Jul 26 '18 at 14:39
  • $\begingroup$ Possibly relevant: cstheory.stackexchange.com/questions/37461/…. $\endgroup$ – Yuval Filmus Jul 26 '18 at 21:31
2
$\begingroup$

Suppose that we are given an instance of EXACT 3-COVER (in which every set contains 3 elements) with $m$ sets on $n$ elements; EXACT 3-COVER is known to be NP-complete. Create a new instance in which each element is replicated $t$ times, each of the original $m$ sets contains each copy of each element, and additionally all $tn$ singletons are available. When the original EXACT 3-COVER instance is a YES instance, the new instance can be exactly covered using at most $m$ sets. When the original EXACT 3-COVER is a NO instance, every exact cover of the new instance requires at least $t$ sets (since every disjoint union of the original sets misses at least one original element, and so requires $t$ singletons in the new instance).

Now let us choose $t = mn^\theta$, for some constant $\theta$. The new instance contains $N = mn^{1+\theta} \leq n^{4+\theta}$ elements, and has a gap of $n^\theta \geq N^{\theta/(4+\theta)}$ between the YES and NO instances. As $\theta \to \infty$, the ratio $\theta/(4+\theta)$ approaches $1$. We conclude that your problem is NP-hard to approximate to within $n^{1-\epsilon}$ for any $\epsilon > 0$. In contrast, there is a trivial $n$-approximation algorithm, which just takes all the singletons.

$\endgroup$
  • $\begingroup$ Very nice idea! One thing: isn't $N = mn^{1 + \theta}$? It doesn't really matter though - reducing from EXACT-3-COVER, we may assume $m \leq n^3$, which eventually leads to the same result. Thanks for the nice answer. $\endgroup$ – Manuel Lafond Jul 27 '18 at 5:49

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.