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$?

  • $\begingroup$ If I understand you correctly, you mean something a little bit stronger than linear-fpt reduction? See this for instance. $\endgroup$ – Saeed May 15 '14 at 13:02
  • 4
    $\begingroup$ You could use such reductions for tight lower bounds under the strong exponential-time hypothesis (SETH), see win.tue.nl/~nikhil/courses/2013/2WO08/eth-lowerbounds.pdf and especially Section 5 therein. $\endgroup$ – Radu Curticapean May 15 '14 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.