<p>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.</p>

<p>For concreteness, I will define the approximate version of the problem below.</p>

<p>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.</p>

CC BY-SA 3.0
2017-02-03T14:15:38.353Z
@RickyDemer, I think your set is $\{0,\ldots ,7\}$ but I don't get what is the set of subsets. e.g. {{0,1,2,3,4},{3,4,5,6,7},{0},{1},{2},{3},{4},{5},{6},{7}} is not a subset of $\{0,\ldots ,7\}$. I think the definition of xyz is fine, but his definition is not definition of exact set cover and actually it is just a set cover. As wiki explains in exact set cover, each of element of the universe should be in exactly one of the subsets.
Saeed
CC BY-SA 3.0
2017-02-03T15:39:50.937Z
@RickyDemer, After all, I don't see why your example shows that his definition is contradicting. There are two subsets (2/3 * 3 = 2) in your example which they cover the whole set. Perhaps better example was: S={0,1,2,3},{4},{5,6,7} and d=3,U={0..7}, so we need exactly 3 subset to cover the universe but 3 is neither less than d nor more than d. I think OP means $\eta \le 1$ (we cannot fix some $\eta$ and say for this special case it does not work, in fact $\eta$ is redundant in the definition).
Saeed
CC BY-SA 3.0
2017-02-03T15:47:09.887Z
In the case you tried to correct me, I'd say it should be clear from the context of my comment, with my suggestion for checking wiki, that each element should be in exactly one of the elements of S* not S and I don't understand your assertion on this and don't understand how it was possible to interpret it like that. But please note that OP's definition is not same as definition of Exact Cover (e.g. it is not like wiki page), OP actually defines normal set cover. Anyways I downvote this question.
Saeed
CC BY-SA 3.0
2017-02-03T19:40:56.273Z
In the last paragraph of question, OP's exact cover is defined. Replace the word "Exact Cover" with "P", this doesn't change the actual definition of OP and just changes the name. Then let me know how P is similar to the exact cover as defined e.g. in wiki? E.g. where OP states that the frequency of each element in the final subsets is 1?
Saeed
CC BY-SA 3.0
2017-02-04T12:37:57.517Z
@Saeed Yes you are right about my definition is not of Exact set-cover, I am editing it.
xyz
CC BY-SA 3.0
2017-02-04T21:20:10.083Z
I removed my downvote
Saeed
CC BY-SA 3.0
2017-05-14T09:50:57.913Z
I edited the question so that input instances that do not have any exact cover are explicitly considered as NO instances. @xyz: if this was not your intention, please revert. In light of this edit i think Ricky Demers answer can be polished into a solid answer to this question.
daniello
<cc.complexity-theory><reference-request><np-hardness><np-complete>
Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?
xyz
# Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?

(Asked by: username_0 on 2017-02-03)

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

**Tags:** cc.complexity-theory, reference-request, np-hardness, np-complete

> **Comments:**
> **username_1**: @RickyDemer, I think your set is $\{0,\ldots ,7\}$ but I don't get what is the set of subsets. e.g. {{0,1,2,3,4},{3,4,5,6,7},{0},{1},{2},{3},{4},{5},{6},{7}} is not a subset of $\{0,\ldots ,7\}$. I think the definition of username_0 is fine, but his definition is not definition of exact set cover and actually it is just a set cover. As wiki explains in exact set cover, each of element of the universe should be in exactly one of the subsets.  
> **username_1**: @RickyDemer, After all, I don't see why your example shows that his definition is contradicting. There are two subsets (2/3 * 3 = 2) in your example which they cover the whole set. Perhaps better example was: S={0,1,2,3},{4},{5,6,7} and d=3,U={0..7}, so we need exactly 3 subset to cover the universe but 3 is neither less than d nor more than d. I think OP means $\eta \le 1$ (we cannot fix some $\eta$ and say for this special case it does not work, in fact $\eta$ is redundant in the definition).  
> **username_1**: In the case you tried to correct me, I'd say it should be clear from the context of my comment, with my suggestion for checking wiki, that each element should be in exactly one of the elements of S* not S and I don't understand your assertion on this and don't understand how it was possible to interpret it like that. But please note that OP's definition is not same as definition of Exact Cover (e.g. it is not like wiki page), OP actually defines normal set cover. Anyways I downvote this question.  
> **username_1**: In the last paragraph of question, OP's exact cover is defined. Replace the word "Exact Cover" with "P", this doesn't change the actual definition of OP and just changes the name. Then let me know how P is similar to the exact cover as defined e.g. in wiki? E.g. where OP states that the frequency of each element in the final subsets is 1?  
> **username_0**: @username_1 Yes you are right about my definition is not of Exact set-cover, I am editing it.  
> **username_1**: I removed my downvote  
> **username_2**: I edited the question so that input instances that do not have any exact cover are explicitly considered as NO instances. @username_0: if this was not your intention, please revert. In light of this edit i think Ricky Demers answer can be polished into a solid answer to this question.  

---

## 0 answers

