Parameterized complexity of Exact Cover 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$?
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 &amp; Grohe), and therefore lies in W[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.
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.
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.