I am working on the decision version of an NP-complete problem. The problem is known to be fixed parameter tractable(FPT) with respect to the solution size $k$ as the parameter.

If I consider another parameter (e.g. $p$), then which among the two following statements holds true?

  1. if $p \leq f(k)$, since the problem is FPT with respect to $k$ it will also be FPT with respect to to $p$.
  2. if $k \leq f(p)$, since the problem is FPT with respect to $k$ it will also be FPT with respect to to $p$.

And another query is that, if a problem is FPT with respect to $m$, then it is also known to be FPT with respect to $n$, given that $m \leq n$. Can someone elaborate on the reason behind this. For example, any problem known to be FPT w.r.t the parameter Treewidth is also FPT w.r.t to another parameter Vertex cover as Treewidth $\leq$ Vertex cover?

  • 3
    $\begingroup$ You might want to give more context for you interest in this question because, as written, it very much looks like an assignment from a grad course rather than the research questions that this community shares and comments upon. $\endgroup$
    – Jérémy
    Aug 3 at 23:03
  • $\begingroup$ These were the two genuine questions I had, and I cannot disclose the problem that I am working on for some reasons. And I don't know how people just assume things. Thanks anyways. $\endgroup$ Aug 4 at 4:59
  • $\begingroup$ By giving the context, I do not mean disclosing the specific problem that you are working on, but rather your area of research (e.g. Operating Systems, Mathematics, etc), and the "context" of your interest in a theme of Theoretical Computer Science. $\endgroup$
    – Jérémy
    Aug 4 at 11:16
  • $\begingroup$ You might want to study the definition of FPT on en.wikipedia.org/wiki/Parameterized_complexity, and if you need more examples, one of the many books on the subject (e.g. I recommend link.springer.com/book/10.1007/978-1-4612-0515-9) $\endgroup$
    – Jérémy
    Aug 4 at 11:19


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.