# Why is dominating set in $W$, but independent set in $W$

In Parameterized Complexity the Independent Set Problem for a Parameter $$k$$ ist $$W$$-complete, and Dominating set is $$W$$-complete. Now the prototypical $$W$$ 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$$ 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$$ 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$$, but that is not true as I know.

EDIT: I took the Turing machine definition of $$W$$ 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$$. 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).

• Could you give references for your NTM characterizations of W and W? 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. – kne Nov 10 '18 at 5:09
• @kne I added some references. – StefanH Nov 10 '18 at 18:13
• Ah, sorry. You did use the word "problem". Yet somehow I read "machine characterization" into it. My fault. – kne Nov 10 '18 at 20:01

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.)