0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

Generally, if

  1. you can solve a problem in time $f(k) \cdot n^{O(1)}$, for a monotone $f$,
  2. and you know that $g(p) \geq k$

then certainly you can solve the problem in time $f(g(p)) \cdot n^{O(1)}$.

If $\text{VC} \geq \text{TW}$ and you can solve a problem in time $f(\text{TW}) \cdot n^{O(1)}$ time, then clearly you can solve the problem in time $f(\text{VC}) \cdot n^{O(1)}$ time, since this is just more time available.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.