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..y B..y
    Aug 3, 2022 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, 2022 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..y B..y
    Aug 4, 2022 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..y B..y
    Aug 4, 2022 at 11:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.