Theoretical Computer Science

Instance of FPT-reductions that is not a polynomial-time reduction

In parametrized complexity people use fixed-parameter-tractable (FPT) reduction to prove W[t]-hardness. Theoretically a FPT-reduction is not a polynomial-time reduction, since it can run exponentially in the parameter k. But in practice all the FPT-reductions I've seen are p-time reductions, which means W[t]-hardness proofs almost always imply NP-completeness proofs.

I wonder if someone can give me a FPT-reduction that indeed runs exponentially in the parameter $k$. Thanks.


An early example is the W[2]-hardness proof for Tournament Dominating Set (Theorem 4.1 in [1]). The reduction is from Dominating Set and it constructs a tournament with $O(2^k n)$ vertices, where $n$ is the number of vertices of the dominating set instance and $k$ is the parameter.

[1]: Rodney G. Downey and Michael R. Fellows. Parameterized computational feasibility. In P. Clote and J.B. Remmel, editors, Proceedings of Feasible Mathematics II, pages 219-244. Birkhauser, 1995.

Comments (1)

  • +1 – A (maybe different) proof of the same statement can also be found in the book "Parameterized Complexity Theory" from J. Flum and M. Grohe, Theorem 7.17. — Jan 07, 2011 at 19:01