<p>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).</p>

<p>D. Marx. <a href="http://siamdl.aip.org/getabs/servlet/GetabsServlet?prog=normal&amp;id=SMJCAT000038000004001382000001&amp;idtype=cvips&amp;gifs=Yes&amp;ref=no">Closest substring problems with small distances</a>. SIAM Journal on Computing, 38(4):1382-1410, 2008.</p>

CC BY-SA 2.5
2011-01-12T08:37:37.587Z
2011-01-12T09:17:32.167Z
2011-01-12T09:17:32.167Z
Daniel Marx
<p>As a complement to the other answers, the following Proposition shows that the corresponding notions of reducibility are incomparable:</p>

<blockquote>
  <p><strong>Proposition [2, Prop. 2.8].</strong> There are parameterized problems $(Q,k)$ and $(Q&#39;,k&#39;)$ such that
  $(Q,k) &lt;^{\mathrm{fpt}} (Q&#39;,k&#39;)$ and $Q&#39; &lt;^{\mathrm{ptime}}\ Q$.</p>
</blockquote>

<p>Here, $&lt;^{\mathrm{fpt}}$ stands for <em>fpt</em>-reduction and $&lt;^{\mathrm{ptime}}$ stands for polynomial-time reduction.</p>

<p>[2]: J. Flum, M. Grohe. Parameterized Complexity Theory. Springer (2006)</p>

CC BY-SA 2.5
2011-01-07T19:17:39.473Z
2011-01-08T13:08:33.173Z
2011-01-08T13:08:33.173Z
Mathieu Chapelle
<p>Probably this is not an intended answer, but how about (a derandomized variant of) color-coding for the k-path problem?  <a href="http://en.wikipedia.org/wiki/Color-coding" rel="nofollow">http://en.wikipedia.org/wiki/Color-coding</a></p>

<p>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.</p>

CC BY-SA 2.5
2011-01-07T17:15:08.110Z
2011-01-07T17:15:08.110Z
Yoshio Okamoto
<p>Another example of such a reduction is the hardness proof for VC-dimension. See "Parameterized learning complexity" by Downey, Evans and Fellows.</p>

CC BY-SA 2.5
2011-01-10T22:43:32.983Z
2011-01-10T22:43:32.983Z
Michael Lampis
<p>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.</p>

<p>[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.</p>

CC BY-SA 2.5
2011-01-07T19:01:22.793Z
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.
Mathieu Chapelle
CC BY-SA 2.5
2011-01-07T18:01:47.693Z
2011-01-07T18:01:47.693Z
Serge Gaspers
<p>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.</p>

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

<cc.complexity-theory><np-hardness><reductions><parameterized-complexity>
Instance of FPT-reductions that is not a polynomial-time reduction
yzll
# Instance of FPT-reductions that is not a polynomial-time reduction

(Asked by: username_0 on 2011-01-07)

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.

**Tags:** cc.complexity-theory, np-hardness, reductions, parameterized-complexity


---

## 5 answers

### Answer by username_5 on 2011-01-07. Score: 11 | Accepted answer

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

---

### Answer by username_1 on 2011-01-12. Score: 9

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](http://siamdl.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000038000004001382000001&idtype=cvips&gifs=Yes&ref=no). SIAM Journal on Computing, 38(4):1382-1410, 2008.


---

### Answer by username_2 on 2011-01-07. Score: 6

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)


---

### Answer by username_3 on 2011-01-07. Score: 5

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.


---

### Answer by username_4 on 2011-01-10. Score: 3

Another example of such a reduction is the hardness proof for VC-dimension. See "Parameterized learning complexity" by Downey, Evans and Fellows.


---

