<p>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 <span class="math-container">$k$</span> as the parameter.</p>
<p>If I consider another parameter (e.g. <span class="math-container">$p$</span>), then which among the two following statements holds true?</p>
<ol>
<li>if <span class="math-container">$p \leq f(k)$</span>, since the problem is FPT with respect to <span class="math-container">$k$</span> it will also be FPT with respect to to <span class="math-container">$p$</span>.</li>
<li>if <span class="math-container">$k \leq f(p)$</span>, since the problem is FPT with respect to <span class="math-container">$k$</span> it will also be FPT with respect to to <span class="math-container">$p$</span>.</li>
</ol>
<p>And another query is that, if a problem is FPT with respect to <span class="math-container">$m$</span>, then it is also known to be FPT with respect to <span class="math-container">$n$</span>, given that <span class="math-container">$m \leq n$</span>. 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 <span class="math-container">$\leq$</span> Vertex cover?</p>

CC BY-SA 4.0
2022-08-03T23:03:29.520Z
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.
J.y B.y
CC BY-SA 4.0
2022-08-04T04:59:41.267Z
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.
Balchandar Reddy
CC BY-SA 4.0
2022-08-04T11:16:11.710Z
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.
J.y B.y
CC BY-SA 4.0
2022-08-04T11:19:16.063Z
You might want to study the definition of FPT on https://en.wikipedia.org/wiki/Parameterized_complexity, and if you need more examples,
one of the many books on the subject (e.g. I recommend https://link.springer.com/book/10.1007/978-1-4612-0515-9)
J.y B.y
<np-hardness><parameterized-complexity><fixed-parameter-tractable>
Tractability with respect to multiple parameters
Balchandar Reddy
# Tractability with respect to multiple parameters

(Asked by: username_0 on 2022-08-03)

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?

**Tags:** np-hardness, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_1**: You might want to study the definition of FPT on https://en.wikipedia.org/wiki/Parameterized_complexity, and if you need more examples, one of the many books on the subject (e.g. I recommend https://link.springer.com/book/10.1007/978-1-4612-0515-9)  

---

## 0 answers

