3
$\begingroup$

In Parameterized Complexity the Independent Set Problem for a Parameter $k$ ist $W[1]$-complete, and Dominating set is $W[2]$-complete. Now the prototypical $W[1]$ problem is deciding by a single-tape non-deterministic Turing machines if it has an accepting run with at most $k$ stepts, and for $W[2]$ it is the same notion with a multitape machine.

Intuitively they are both set selection problems, so a non-deterministic machine can guess in at most $k$ steps what elements to take into an independent (or dominating) set. So with this intuition, that the first problem ist in $W[1]$ is clear, but not why dominating set is not? So what am I missing, what is the distinguishing feature, why do we need a multitape machine for the second, but not for the first? My gut feeling would put domination set into $W[1]$, but that is not true as I know.

EDIT: I took the Turing machine definition of $W[1]$ from the following seminal paper Fixed-Parameter Tractability and Completeness I: Basic Results, but it is also written on wikipedia, together with the characterisation of $W[2]$. If you do not have access to the paper you can get a pdf from here, but the diagrams are missing in there (see page 6 for the definition of the Turing machine problem).

$\endgroup$
  • $\begingroup$ Could you give references for your NTM characterizations of W[1] and W[2]? Not only am I not aware of them, but also I believe them to be false. The nondeterminism of NTMs has fixed-size branching, so in $k$ steps only $2^{O(k)}$ configurations can be reached. Which is in FPT. $\endgroup$ – kne Nov 10 '18 at 5:09
  • $\begingroup$ @kne I added some references. $\endgroup$ – StefanH Nov 10 '18 at 18:13
  • $\begingroup$ Ah, sorry. You did use the word "problem". Yet somehow I read "machine characterization" into it. My fault. $\endgroup$ – kne Nov 10 '18 at 20:01
2
$\begingroup$

For deciding the independent or dominating set problem, it is not sufficient to guess the set. One must also verify that the guessed set indeed is an independent or a dominating set.

In the case of independent set, once the machine has guessed the set and stored it in the first $k$ cells of the tape, it checks for all pairs of guessed vertices whether they are indeed not equal and do not form an edge. There are $k\choose 2$ such pairs, so the overall running time is $O(k^2)$. Thus the reduction from independend set to short NTM acceptance is a parameterized reduction. The number of steps in the verification phase only depends on the parameter.

In the case of dominating set, one needs to checks whether all vertices are dominated. While above, we only had $k\choose 2$ pairs, now we have to deal with $n$ vertices. Which does not only depend on the parameter. (The way the multitape NTM solves this is by spending one tape per vertex.)

Of course, the above is only intended to give some intuition about why dominating set is not in W[1]. It does not give a proof. That would be way out of scope...

(For the sake of the casual reader, let me clarify that the NTMs above are not machines that solve the independent or dominating set problem. There is a reduction involved that converts instances of these problems into machines. Thus, a single such machine solves only a single instance of the problem, not the general problem.)

$\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.