Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
The following paper contains reductions for various parameterizations of Closest Substring where the running time depends exponentially or double exponentially on the parameter (and this dependence seems to be unavoidable).
D. Marx. Closest substring problems with small distances. SIAM Journal on Computing, 38(4):1382-1410, 2008.
As a complement to the other answers, the following Proposition shows that the corresponding notions of reducibility are incomparable:
Proposition [2, Prop. 2.8]. There are parameterized problems $(Q,k)$ and $(Q',k')$ such that $(Q,k) <^{\mathrm{fpt}} (Q',k')$ and $Q' <^{\mathrm{ptime}}\ Q$.
Here, $<^{\mathrm{fpt}}$ stands for fpt-reduction and $<^{\mathrm{ptime}}$ stands for polynomial-time reduction.
[2]: J. Flum, M. Grohe. Parameterized Complexity Theory. Springer (2006)
Probably this is not an intended answer, but how about (a derandomized variant of) color-coding for the k-path problem? http://en.wikipedia.org/wiki/Color-coding
There, one transforms an instance of the k-path problem to instances of the colorful k-path problem by an fpt-reduction with super-polynomial dependency on k. (One creates multiple instances, but they can be seen as one big instance.) Since the colorful k-path problem can be solved in fpt time by dynamic programming, we can conclude the k-path problem belongs to FPT.
Another example of such a reduction is the hardness proof for VC-dimension. See "Parameterized learning complexity" by Downey, Evans and Fellows.
