<p>An FPT-reduction between parameterized problems $P$ and $Q$ is a pair of functions $f$ and $p$, such that every instance $x$ of $P$ with parameter $k$ is mapped to an instance $f(x,k)$ of $Q$ with parameter at most $p(k)$, with</p>

<ul>
<li>$f(x,k) \in Q$ iff $x\in P$,</li>
<li>$f(x,k)$ is computed in fixed-parameter tractable time, i.e., in time  $g(k) \cdot |x|^{O(1)}$ for some function $g$.</li>
</ul>

<p>Is there an established name for the stronger type of reduction where $f(x,k)$ does not depend on the parameter $k$, but only on the instance $x$, and $p$ is the identity function?</p>

<p>In other words, $f$ is a polynomial time reduction between the underlying classical problems that does not increase the parameter. Does the existence such a reduction from some $\mathsf{W}[t]$-complete problem to a problem $Q$ have any further consequences beyond the $\mathsf{W}[t]$-hardness of $Q$? </p>

CC BY-SA 3.0
2014-05-15T13:02:19.693Z
If I understand you correctly, you mean something a little bit stronger than linear-fpt reduction? See [this](http://www.cs.lafayette.edu/~gexia/research/jcombopt.pdf) for instance.
Saeed
CC BY-SA 3.0
2014-05-15T14:15:20.883Z
You could use such reductions for tight lower bounds under the strong exponential-time hypothesis (SETH), see http://www.win.tue.nl/~nikhil/courses/2013/2WO08/eth-lowerbounds.pdf and especially Section 5 therein.
Radu Curticapean
<cc.complexity-theory><reference-request><parameterized-complexity>
Stronger reductions in parameterized complexity
Jan Johannsen
# Stronger reductions in parameterized complexity

(Asked by: username_0 on 2014-05-15)

An FPT-reduction between parameterized problems $P$ and $Q$ is a pair of functions $f$ and $p$, such that every instance $x$ of $P$ with parameter $k$ is mapped to an instance $f(x,k)$ of $Q$ with parameter at most $p(k)$, with

* $f(x,k) \in Q$ iff $x\in P$,
* $f(x,k)$ is computed in fixed-parameter tractable time, i.e., in time $g(k) \cdot |x|^{O(1)}$ for some function $g$.

Is there an established name for the stronger type of reduction where $f(x,k)$ does not depend on the parameter $k$, but only on the instance $x$, and $p$ is the identity function?

In other words, $f$ is a polynomial time reduction between the underlying classical problems that does not increase the parameter. Does the existence such a reduction from some $\mathsf{W}[t]$-complete problem to a problem $Q$ have any further consequences beyond the $\mathsf{W}[t]$-hardness of $Q$?

**Tags:** cc.complexity-theory, reference-request, parameterized-complexity

> **Comments:**
> **username_1**: If I understand you correctly, you mean something a little bit stronger than linear-fpt reduction? See [this](http://www.cs.lafayette.edu/~gexia/research/jcombopt.pdf) for instance.  
> **username_2**: You could use such reductions for tight lower bounds under the strong exponential-time hypothesis (SETH), see http://www.win.tue.nl/~nikhil/courses/2013/2WO08/eth-lowerbounds.pdf and especially Section 5 therein.  

---

## 0 answers

