# 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}$-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. It is recognizable by a tail-nondeterministic RAM (as introduced by Flum & 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.

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.

ExactCover is W-complete. The above discussion shows containment in W. Furthermore, ExactCover contains the W-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$?)