7
$\begingroup$

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$?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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