<h2>Correction:</h2>

<p>I have claimed (see below) that "Independent Dominating Set" is a special case of ExactCover. This claim was wrong, as two vertices in the ind-dom set may have overlapping neighborhoods.</p>

<p>In fact, "Exact Cover" is contained in W[1].
It is recognizable by a tail-nondeterministic RAM (as introduced by Flum &amp; Grohe), and therefore lies in W[1]:</p>

<ol>
<li><p>In the preprocessing phase, construct and store a 2-dimensional table
that states for every two subsets $S_i$ and $S_j$ in $S^*$ whether they overlap.
Furthermore, construct a second table that stores for every subset $S_i$ in $S^*$ its cardinality. This clearly can be done in polynomial time.</p></li>
<li><p>In the guessing phase, guess a system of $k$ (indices of) subsets in $S^*$. This clearly can be done in $O(f(k))$ time on a RAM.</p></li>
<li><p>In the verification phase, first check whether any two guessed subsets overlap, by looking up the 2-dimensional table. Then check whether the total size of all guessed subsets equals $|U|$. (The first check guarantees that every element of $U$ is covered at most once, and the second check guarantees that it is covered at least once.) All this can be done in $O(g(k))$ time on a RAM.</p></li>
</ol>

<h2>Correct answer:</h2>

<p>ExactCover is W[1]-complete. The above discussion shows containment in W[1].
Furthermore, ExactCover contains the W[1]-complete PerfectCode problem as a special case. (Given a graph $G$ and an integer $k$. Does $G$ contain a subset $C$ of $k$ vertices, such that every vertex in $G$ is contained in the closed neighborhood of exactly one vertex in $C$?)</p>

<p>R.G. Downey, M.R. Fellows
Fixed-parameter tractability and completeness. II. On completeness for W[1]
Theoretical Computer Science 141 (1995), pp. 109–131</p>

<hr>

<h2>Old (wrong) answer, left for reference:</h2>

<p>"Independent Dominating Set" is W[2]-complete, and a special case
of your ExactCover problem:</p>

<p>R.G. Downey and M.R. Fellows. 
Fixed-parameter tractability and completeness. 
Congressus Numerantium 87:161–178, 1992.</p>

CC BY-SA 3.0
2015-01-12T12:20:50.100Z
2015-01-12T17:31:30.607Z
2015-01-12T17:31:30.607Z
Gamow
<p>Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and an integer $K$, find whether there exists a subcollection $\mathcal{S}^* \subseteq \mathcal{S}$ such that $|\mathcal{S}^*| = K$ and such that each element of $U$ is contained by exactly one subset from $\mathcal{S}^*$.</p>

<p>What is parameterized complexity of the $\mathrm{ExactCover}$ problem for the parameter $K$ (the number of sets used in coverage)? It is known that  $\mathrm{SetCover}$ is $\mathrm{W}[2]$-complete, but is there anything known about $\mathrm{ExactCover}$ for $K$?</p>

<parameterized-complexity><set-cover><exact-cover>
Parameterized complexity of Exact Cover
Piotr Skowron
# Parameterized complexity of Exact Cover

(Asked by: username_0 on 2015-01-12)

Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and an integer $K$, find whether there exists a subcollection $\mathcal{S}^\* \subseteq \mathcal{S}$ such that $|\mathcal{S}^\*| = K$ and such that each element of $U$ is contained by exactly one subset from $\mathcal{S}^\*$.

What is parameterized complexity of the $\mathrm{ExactCover}$ problem for the parameter $K$ (the number of sets used in coverage)? It is known that $\mathrm{SetCover}$ is $\mathrm{W}[2]$-complete, but is there anything known about $\mathrm{ExactCover}$ for $K$?

**Tags:** parameterized-complexity, set-cover, exact-cover


---

## 1 answers

### Answer by username_1 on 2015-01-12. Score: 7 | Accepted answer

## Correction:

I have claimed (see below) that "Independent Dominating Set" is a special case of ExactCover. This claim was wrong, as two vertices in the ind-dom set may have overlapping neighborhoods.

In fact, "Exact Cover" is contained in W[1].
It is recognizable by a tail-nondeterministic RAM (as introduced by Flum & Grohe), and therefore lies in W[1]:

1. In the preprocessing phase, construct and store a 2-dimensional table
   that states for every two subsets $S\_i$ and $S\_j$ in $S^\*$ whether they overlap.
   Furthermore, construct a second table that stores for every subset $S\_i$ in $S^\*$ its cardinality. This clearly can be done in polynomial time.
2. In the guessing phase, guess a system of $k$ (indices of) subsets in $S^\*$. This clearly can be done in $O(f(k))$ time on a RAM.
3. In the verification phase, first check whether any two guessed subsets overlap, by looking up the 2-dimensional table. Then check whether the total size of all guessed subsets equals $|U|$. (The first check guarantees that every element of $U$ is covered at most once, and the second check guarantees that it is covered at least once.) All this can be done in $O(g(k))$ time on a RAM.

## Correct answer:

ExactCover is W[1]-complete. The above discussion shows containment in W[1].
Furthermore, ExactCover contains the W[1]-complete PerfectCode problem as a special case. (Given a graph $G$ and an integer $k$. Does $G$ contain a subset $C$ of $k$ vertices, such that every vertex in $G$ is contained in the closed neighborhood of exactly one vertex in $C$?)

R.G. Downey, M.R. Fellows
Fixed-parameter tractability and completeness. II. On completeness for W[1]
Theoretical Computer Science 141 (1995), pp. 109–131

---

## Old (wrong) answer, left for reference:

"Independent Dominating Set" is W[2]-complete, and a special case
of your ExactCover problem:

R.G. Downey and M.R. Fellows.
Fixed-parameter tractability and completeness.
Congressus Numerantium 87:161–178, 1992.


---

