-1
$\begingroup$

I am a research scholar, currently working on parameterized algorithms. I am working on a problem and have been exploring various parameters for which the problem remains unsolved. I have read the following paper on formulating fixed parameter tractable algorithms for Twin cover.

1.Ganian, Robert, Twin-cover: beyond vertex cover in parameterized algorithmics, Marx, Dániel (ed.) et al., Parameterized and exact computation. 6th international symposium, IPEC 2011, Saarbrücken, Germany, September 6–8, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28049-8/pbk). Lecture Notes in Computer Science 7112, 259-271 (2012). ZBL1352.68105.

Even though i understand all the techniques described in this paper, I did not understand how a problem is fixed parameter tractable with respect to a larger parameter(vertex cover in this case) if it is fixed parameter tractable with respect to a smaller parameter(twin cover in this case). The problem i am working on is proved to be fixed parameter tractable with respect to the vertex cover and it is open when parameterized by twin cover. Could someone elaborate on this?

$\endgroup$
1
  • 1
    $\begingroup$ If a problem is fpt wrt a smaller parameter, it is also fpt wrt a larger parameter. E.g., if you have an efficient algorithm for graphs with twin cover $\le k$, then you also have an efficient algorithm for graphs with vertex cover $\le k$, as any such graph must have twin cover $\le k$ as well, hence you can apply the first algorithm. In general, no such reduction works in the opposite direction. $\endgroup$ Aug 5 at 13:17

1 Answer 1

-1
$\begingroup$

Consider a pair $(Pb,d)$ formed by a NP-hard decision problem $Pb$ and two parameters / measures of difficulty $d(I)$ and $d'(I)$ on any legal input $I$ for it, in additional to its size $n(I)$. Assume that the worst case complexity of $Pb$ is non decreasing with $n$, $d$ and $d'$. Let's establish some basic notions:

  • Saying that $Pb$ can be solved in time within $O(t(n))$ means that there is an algorithm which runs in time within $O(t(n))$;
  • Saying that $Pb$'s worst case complexity is within $\Omega(t(n))$ (i.e. in $\Theta(t(n))$ if it is also within $O(t(n))$) means that no algorithm can ALWAYS run in time within $o(t(n))$;
  • Saying that $Pb$ is in $NP$ means that correctness of a certificate of its output can be checked in time polynomial in $n$;
  • Saying that $Pb$ is $NP$-hard means that other problems from $NP$ can be reduced in time polynomial in $n$ to $Pb$, such that if $Pb$ could be solved in time polynomial in $n$, all $NP$ problems could too;
  • Saying that $Pb$ is fixed parameter tractable with respect to a parameter $d(I)$ (i.e. $(Pb,d)\in FPT$) means that there is an algorithm solving $Pb$ which running time is polynomial in the input size $n$ in the worst case over all instances with a FIXED value of $d(I)$ (e.g. $t(n)=n^d$ is polynomial in $n$ for fixed values of $d$, while $d^n$ is not).

Say that

  1. $d(I)\leq d'(I)$ on any legal instance $I$ of $Pb$, and that
  2. $(Pb,d)\in FPT$:

Then

  • according to (2.), there is an algorithm solving $Pb$ which running time is polynomial in $n$ over all instances with a fixed value of $d(I)$;
  • according to (1.), this algorithm is solving $Pb$ in time polynomial in $n$ over all instances with fixed value of $d'(I)$, since $d(I)\leq d'(I)$ and a fixed value of $d'(I)$ will put an upper bound on $d(I)$

So that $(Pb,d')\in FPT$. The reverse implication is not true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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