1
$\begingroup$

Question

While trying to search for a (example of a) NP-hard problem that fixed-parameter reduces to another NP-hard problem that is known to be fixed parameter tractable, such as k-Vertex Cover, my search results are "poluted" by papers establishing $W[1]$ hardness through parameterized reductions.

It is stated in numerous sources that if one can complete a fpt reduction from NP-hard problem $K-D$ to the parameterization $K'-D'$ of another NP-hard problem, where $K'-D'$ is FPT, then $K-D$ is FPT as well.

But I am experiencing some difficulties finding a single example of such a parameterized reduction. Hence I would like to ask:

Does there exist a fixed-parameter tractable reduction of a parameterisation $K-D$ of a NP-hard problem towards a fixed-parameter tractable parameterisation $K'-D' \in FPT$? (Where $D\neq D'$)

Doubts

  1. Most likely my search queries are not good enough, but I do not know how to verify this without evaluating all information, developing some increadibly difficult proof, or an authoritarian input. The first two options are currently considered unfeasible by me. This is my third option.
  2. I am aware that it is generally more easy to show something is difficult~ something is not FPT (establishing non-trivial $W[1]$ hardness), than it is to show something is (relatively) easy (showing something is FPT). However since some problems are already shown to be FPT, such as $k-Vertex Cover$, $k-Max Cut$, $k-Subset Sum$ etc. I would expect at least some parameterized reductions from an NP-hard problem towards a parameterization that is shown to be FPT. So most likely, I need to search more effectively.
$\endgroup$

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.