<p>Consider a pair <span class="math-container">$(Pb,d)$</span> formed by a NP-hard decision problem <span class="math-container">$Pb$</span> and two parameters / measures of difficulty <span class="math-container">$d(I)$</span>  and <span class="math-container">$d'(I)$</span> on any legal input <span class="math-container">$I$</span> for it, in additional to its size <span class="math-container">$n(I)$</span>. Assume that the worst case complexity of <span class="math-container">$Pb$</span> is non decreasing with <span class="math-container">$n$</span>, <span class="math-container">$d$</span> and <span class="math-container">$d'$</span>. Let's establish some basic notions:</p>
<ul>
<li>Saying that <span class="math-container">$Pb$</span> can be solved in time within <span class="math-container">$O(t(n))$</span> means that there is an algorithm which runs in time within <span class="math-container">$O(t(n))$</span>;</li>
<li>Saying that <span class="math-container">$Pb$</span>'s worst case complexity is within <span class="math-container">$\Omega(t(n))$</span> (i.e. in <span class="math-container">$\Theta(t(n))$</span> if it is also within <span class="math-container">$O(t(n))$</span>) means that no algorithm can ALWAYS run in time within <span class="math-container">$o(t(n))$</span>;</li>
<li>Saying that <span class="math-container">$Pb$</span> is in <span class="math-container">$NP$</span> means that correctness of a certificate of its output can be checked in time polynomial in <span class="math-container">$n$</span>;</li>
<li>Saying that <span class="math-container">$Pb$</span> is <span class="math-container">$NP$</span>-hard means that other problems from <span class="math-container">$NP$</span> can be reduced in time polynomial in <span class="math-container">$n$</span> to <span class="math-container">$Pb$</span>, such that if <span class="math-container">$Pb$</span> could be solved in time polynomial in <span class="math-container">$n$</span>, all <span class="math-container">$NP$</span> problems could too;</li>
<li>Saying that <span class="math-container">$Pb$</span> is fixed parameter tractable with respect to a parameter <span class="math-container">$d(I)$</span> (i.e. <span class="math-container">$(Pb,d)\in FPT$</span>) means that there is an algorithm solving <span class="math-container">$Pb$</span> which running time is polynomial in the input size <span class="math-container">$n$</span> in the worst case   over all instances with a FIXED value of <span class="math-container">$d(I)$</span> (e.g. <span class="math-container">$t(n)=n^d$</span> is polynomial in <span class="math-container">$n$</span> for fixed values of <span class="math-container">$d$</span>, while <span class="math-container">$d^n$</span> is not).</li>
</ul>
<p>Say that</p>
<ol>
<li><span class="math-container">$d(I)\leq d'(I)$</span>  on any legal instance <span class="math-container">$I$</span> of <span class="math-container">$Pb$</span>, and that</li>
<li><span class="math-container">$(Pb,d)\in FPT$</span>:</li>
</ol>
<p>Then</p>
<ul>
<li>according to (2.), there is an algorithm solving <span class="math-container">$Pb$</span> which running time is polynomial in <span class="math-container">$n$</span> over all instances with a fixed value of <span class="math-container">$d(I)$</span>;</li>
<li>according to (1.), this algorithm is solving <span class="math-container">$Pb$</span> in time polynomial in <span class="math-container">$n$</span> over all instances with fixed value of <span class="math-container">$d'(I)$</span>, since <span class="math-container">$d(I)\leq d'(I)$</span> and a fixed value of <span class="math-container">$d'(I)$</span> will put an upper bound on <span class="math-container">$d(I)$</span></li>
</ul>
<p>So that <span class="math-container">$(Pb,d')\in FPT$</span>.
The reverse implication is not true.</p>

CC BY-SA 4.0
2022-08-22T11:24:45.760Z
Hi @Jeremy, I was wondering whether there is any content or papers on proving W[1]-hardness for a problem when parameterized by the Twin cover, I don't seem to find any. How one may proceed in solving this? any suggestions will be helpful. TIA.
Balchandar Reddy
CC BY-SA 4.0
2022-08-23T10:24:38.083Z
Sorry, I am not a specialist on Parameterized Complexity, and even less about (the size of the) twin cover as a parameter.
J.y B.y
CC BY-SA 4.0
2022-08-06T15:06:58.947Z
2022-08-08T11:22:00.490Z
2022-08-08T11:22:00.490Z
J.y B.y
<p>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.</p>
<p>1.<em>Ganian, Robert</em>, <a href="http://dx.doi.org/10.1007/978-3-642-28050-4_21" rel="nofollow noreferrer"><strong>Twin-cover: beyond vertex cover in parameterized algorithmics</strong></a>, 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). <a href="https://zbmath.org/?q=an:1352.68105" rel="nofollow noreferrer">ZBL1352.68105</a>.</p>
<p>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?</p>

CC BY-SA 4.0
2022-08-05T13:17:59.990Z
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.
Emil Jeřábek
<np-hardness><parameterized-complexity><fixed-parameter-tractable>
Parameters: Twin cover and Vertex cover
Balchandar Reddy
# Parameters: Twin cover and Vertex cover

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

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**](http://dx.doi.org/10.1007/978-3-642-28050-4_21), 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](https://zbmath.org/?q=an:1352.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?

**Tags:** np-hardness, parameterized-complexity, fixed-parameter-tractable

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2022-08-06. Score: -1

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.

> **Comments:**
> **username_0**: Hi @Jeremy, I was wondering whether there is any content or papers on proving W[1]-hardness for a problem when parameterized by the Twin cover, I don't seem to find any. How one may proceed in solving this? any suggestions will be helpful. TIA.  
> **username_2**: Sorry, I am not a specialist on Parameterized Complexity, and even less about (the size of the) twin cover as a parameter.  

---

