 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. ## Solution

An early example is the W-hardness proof for Tournament Dominating Set (Theorem 4.1 in ). 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.

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