0
$\begingroup$

$FPT$ is the set of parameterized problems that are fixed-parameter tractable. If $L_{w,h}$ is the language associated to boolean circuits of weft $w$ and depth $h$, then $W[t]$ is the set of parameterized problems that can be fixed-parameter reduced to $L_{t,h}$ for some constant $h$. (I know that there are multiple equivalent definitions.) It is folklore that

$$ FPT \subseteq W[1] \subseteq W[2] \subseteq \dots $$

but I do not really understand the first inclusion, and I could not find a satisfying explanation.

Niedermeier writes in "Invitation to Fixed-Parameter Algorithms" that "The inclusion $FPT \subseteq W[1]$ directly follows from the fact that $W[1]$ allows '$FPT$-computations' through the use of parameterized reductions". What is meant by that?

$\endgroup$

1 Answer 1

1
$\begingroup$

A problem $P$ in FPT has a parametrized reduction to any parametrized decision problem that has at least one "true" and "false" instance. The reduction algorithm has enough time to compute whether an instance of $P$ is true or false (because $P$ is in FPT), and can then simply map it to one of the true or false instances of the other language.

So, the problem $P$ has a parametrized reduction to $L_{1,1}$ in particular, and therefore is in $W[1]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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