4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ When ​ $\eta = 2/3$ , ​ ​ ​ ( {0,1,2,3,4,5,6,7} , {{0,1,2,3,4},{3,4,5,6,7},{0},{1},{2},{3},{4},{5},{6},{7}} , 3 ) ​ simultaneously satisfies your conditions for being a yes instance and being a no instance. $\;\;\;\;$ $\endgroup$ – user6973 Feb 3 '17 at 12:05
  • $\begingroup$ @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. $\endgroup$ – Saeed Feb 3 '17 at 14:15
  • $\begingroup$ @Saeed : ​ ​ ​ ​ ​ ​ ​ The set of subsets is {{0,1,2,3,4},{3,4,5,6,7},{0},{1},{2},{3},{4},{5},{6},{7}}. ​ (Each element of {{0,1,2,3,4},{3,4,5,6,7},{0},{1},{2},{3},{4},{5},{6},{7}} is a subset of {0,1,2,3,4,5,6,7}.) ​ "each of element of the universe should be in exactly one of the" elements of $S^*$, not necessarily "in exactly one of the" elements of $S$. ​ ​ ​ Otherwise, ​ $S^* = S$ ​ would always be a (in fact, the only) solution. ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user6973 Feb 3 '17 at 14:23
  • $\begingroup$ @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). $\endgroup$ – Saeed Feb 3 '17 at 15:39
  • $\begingroup$ 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. $\endgroup$ – Saeed Feb 3 '17 at 15:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The idea seems fine, but the description is a little hard to follow. Might be easier to reduce from 1-in-3-SAT. [Note to @xyz: he is giving a reduction where there is an exact cover (of any size) if and only if the formula is satisfiable.] $\endgroup$ – Neal Young Mar 14 '17 at 18:38
  • $\begingroup$ Is Exact 3D Matching known to be ETH hard? If it is, it would make for a simpler answer. $\endgroup$ – daniello May 14 '17 at 10:36

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.