<p>It's also NP-hard, because Set Cover on sets of constant size is NP-hard, and given an instance of Set Cover with constant-size sets, you can add all the (polynomially many) subsets of the given sets, and you will obtain a new instance which is equivalent (has the same min-size set cover) but also has an exact cover of the same size as the min-size set cover.</p>

CC BY-SA 4.0
2023-03-08T05:04:56.967Z
Thank you! This is a really cute reduction that I'm kicking myself for not thinking of haha.
Matthew Ferland
CC BY-SA 4.0
2023-03-08T00:14:51.987Z
2023-03-08T00:14:51.987Z
Neal Young
<p>As stated in the question, I'm interested in a variant of Exact Cover that is currently relevant to my research. Specifically, a variant where you are promised that if there is a Set Cover of size <span class="math-container">$k$</span>, then there is also an Exact Cover of size <span class="math-container">$k$</span> (or less).</p>
<p>More formally, let us define the Exact Cover and Set Cover problems.</p>
<p><strong>Set Cover</strong>
Given a collection <span class="math-container">$S$</span> of of subsets <span class="math-container">$S_i$</span> of a set <span class="math-container">$X$</span> and a target <span class="math-container">$k$</span>, does there exist a subcollection <span class="math-container">$S^{\ast}$</span> of <span class="math-container">$S$</span> of size <span class="math-container">$k$</span> or less such that every element in <span class="math-container">$X$</span> is contained in <span class="math-container">$S^{\ast}$</span>?</p>
<p><strong>Exact Cover</strong>
Does there exist a Set Cover of size <span class="math-container">$k$</span> such that every element in <span class="math-container">$X$</span> is contained <em>exactly once</em> in <span class="math-container">$S^{\ast}$</span>?</p>
<p>My modification is</p>
<p><strong>Pure Exact Cover</strong>
For a given input, categorize the input into one of two cases:</p>
<ol>
<li>There an Exact Cover of size <span class="math-container">$k$</span> or less,</li>
<li>There is no Set Cover of size <span class="math-container">$k$</span>.</li>
</ol>
<p>You are promised that if there is a Set Cover of size <span class="math-container">$k$</span>, there is also an Exact Cover of size <span class="math-container">$k$</span></p>
<p>Is this Pure Exact Cover problem still NP-hard? Or at least, has this problem been examined at all in the research? I can't find anything, but I also have no idea what name it would have.</p>

CC BY-SA 4.0
2023-03-08T00:20:29.970Z
This is a generalization of the NP-hard **Perfect 3d Matching** problem.
Yonatan N
<np-hardness><set-cover><exact-cover>
Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover
Matthew Ferland
# Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover

(Asked by: username_0 on 2023-03-07)

As stated in the question, I'm interested in a variant of Exact Cover that is currently relevant to my research. Specifically, a variant where you are promised that if there is a Set Cover of size $k$, then there is also an Exact Cover of size $k$ (or less).

More formally, let us define the Exact Cover and Set Cover problems.

**Set Cover**
Given a collection $S$ of of subsets $S\_i$ of a set $X$ and a target $k$, does there exist a subcollection $S^{\ast}$ of $S$ of size $k$ or less such that every element in $X$ is contained in $S^{\ast}$?

**Exact Cover**
Does there exist a Set Cover of size $k$ such that every element in $X$ is contained *exactly once* in $S^{\ast}$?

My modification is

**Pure Exact Cover**
For a given input, categorize the input into one of two cases:

1. There an Exact Cover of size $k$ or less,
2. There is no Set Cover of size $k$.

You are promised that if there is a Set Cover of size $k$, there is also an Exact Cover of size $k$

Is this Pure Exact Cover problem still NP-hard? Or at least, has this problem been examined at all in the research? I can't find anything, but I also have no idea what name it would have.

**Tags:** np-hardness, set-cover, exact-cover
> **Comments:**
> **username_1**: This is a generalization of the NP-hard **Perfect 3d Matching** problem.  

---

## 1 answers

### Answer by username_2 on 2023-03-08. Score: 5 | Accepted answer

It's also NP-hard, because Set Cover on sets of constant size is NP-hard, and given an instance of Set Cover with constant-size sets, you can add all the (polynomially many) subsets of the given sets, and you will obtain a new instance which is equivalent (has the same min-size set cover) but also has an exact cover of the same size as the min-size set cover.

> **Comments:**
> **username_0**: Thank you! This is a really cute reduction that I'm kicking myself for not thinking of haha.  

---

