# Hardness of approximating Minimum Cardinality Exact Cover

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.

• 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? – user53923 Jul 26 '18 at 9:09
• 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. – Manuel Lafond Jul 26 '18 at 14:39
• Possibly relevant: cstheory.stackexchange.com/questions/37461/…. – Yuval Filmus Jul 26 '18 at 21:31

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.
• 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. – Manuel Lafond Jul 27 '18 at 5:49