Theoretical Computer Science
- cc.complexity-theory np-hardness reductions parameterized-complexity
- Updated Thu, 26 May 2022 22:34:07 GMT
-
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[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.