Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard? It is known that Exact Set Cover is an NP-hard problem (Reduction from 3-SAT and 3-Coloring). Also, my minor analysis one can realize that this problem is also ETH-hard, i.e. this cannot be solved in less than $2^{\epsilon n}$ time, unless the Exponential Time Hypothesis(ETH) is false. I want to know whether something can be said about the approximation of Exact Set Cover.

For concreteness, I will define the approximate version of the problem below.

Let $\mathcal{U}$ be the universe and $\mathcal{S}$ be the collection of subsets. Then, an instance of Exact set-cover($\mathcal{U}$,$\mathcal{S}$,$d$) is a yes instance, if there is a collection $\mathcal{S'} \subseteq \mathcal{S}$ with $|\mathcal{S'}| \leq \eta d \quad (\eta &lt;1)$ that exactly covers $\mathcal{U}$ (that is each element of the universe appears in exactly one set in $\mathcal{S'}$). The input instance is a no-instance if there are no exact covers, or all exact covers need more than $d$ subsets. Here $\eta$ (or rather $1/\eta$) is the approximation factor.
Yes, because you made the approximation irrelevant. ​ Reduce from k-SAT:

Each variable contributes one element to $\mathcal{U}$ and each clause

contributes k+1 elements to $\mathcal{U}$, one for each literal and one more.

Each literal contributes one set to $\mathcal{S}$ ​ - ​ The elements are [[the element of $\mathcal{U}$ from

the literal's variable] and [the [elements from the clauses] which are [for that literal]]].

Each clause contributes ​ 2k-1 ​ sets to $\mathcal{S}$ ​ ​ ​ - ​ ​ ​ One for each non-full subset of the set of literals,

but the other element from the clause must be in each of those ​ 2k-1 ​ elements of $\mathcal{S}$.

For a subset of $\mathcal{S}$ to be pairwise disjoint, it cannot have sets from opposite literals and

cannot have more than one set from any given clause. ​ For a subset of $\mathcal{S}$ to cover $\mathcal{U}$,

it must have at least one set from each variable and at least one set from each clause.

Thus exact covers must have exactly one set from each variable and from each clause.

Each element of $\mathcal{S}$ is from

[[no clauses and exactly one variable] or [no variables and exactly one clause]],

so all exact covers have exactly ​ ​ ​ number of variables ​ + ​ number of clauses ​ ​ ​ elements of $\mathcal{S}$.

For any assignment which does not satisfy the k-SAT formula, the subset of $\mathcal{S}$ induced by that assignment is disjoint from at least one clause's set of k+1 elements of $\mathcal{U}$, no other clauses' sets intersect any of those sets of k+1 elements of $\mathcal{U}$, and no single element of $\mathcal{S}$ covers all of those k+1 elements of $\mathcal{U}$. ​ Thus non-satisfying assignments have zero extensions to exact covers.

For any assignment which does satisfy the k-SAT formula, each clause has exactly one element

of $\mathcal{S}$ from the set of that clause's literals which are false, one can trivially find the set of those elements of $\mathcal{S}$, and using that set to extend [the subset of $\mathcal{S}$ induced by the assignment]

gives an exact cover. ​ Since elements of $\mathcal{S}$ from clauses do not have any elements of $\mathcal{U}$

from other clauses, satisfying assignments have no other extensions to exact covers.



Therefore your problem is ETH-hard under strongly parsimonious reductions.