# Parameters: Twin cover and Vertex cover

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?

• 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. Aug 5 at 13:17

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.