<p>We have known how to get a <span class="math-container">$2k$</span> kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC.</p>
<p>My question is, can we do better for planar graphs? It is easy to identify lots of &quot;tight&quot; graphs: a graph has <span class="math-container">$(2k-1)$</span> vertices and its minimum Vertex Cover has size <span class="math-container">$k$</span>.  The only known bound is <span class="math-container">$1.33k$</span> by Chen et al. [2007 SIAM J. COMPUT.]</p>

CC BY-SA 3.0
2012-03-28T18:18:40.840Z
As far as I know, the existence of a 2k-vertex kernel for VC was first shown in "Vertex Cover: Further Observations and Further Improvements" from 2001, so it is just over a decade old rather than three; the k^2-vertex kernel by Buss has been known for longer. As for the question whether we can do better on planar graphs: I know that many people have tried, but none have succeeded.
Bart Jansen
CC BY-SA 3.0
2012-03-29T02:59:14.117Z
If you would like to have a look at Hochbaum's paper (Discrete Applied Mathematics 6 (1983) 243-254), you'll see the 2k kernel there (of coz the name "kernel" was not used).  Actually, your adviser took the same position as me in his survey for IWPEC'09.
Yixin Cao
CC BY-SA 3.0
2012-03-31T02:17:25.170Z
Thanks - I was not aware of Hochbaum's paper. I agree that the idea of a 2k kernel are there (although the meat of it was already in Nemhauser and Trotter's paper, of course). I don't see it being cited in Bodlaender's IWPEC survey, though.
Bart Jansen
<ds.algorithms><planar-graphs><parameterized-complexity><vertex-cover><kernelization>
Can we achieve a better kernel for the Vertex Cover problem on planar graphs?
Yixin Cao
# Can we achieve a better kernel for the Vertex Cover problem on planar graphs?

(Asked by: username_0 on 2012-03-27)

We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC.

My question is, can we do better for planar graphs? It is easy to identify lots of "tight" graphs: a graph has $(2k-1)$ vertices and its minimum Vertex Cover has size $k$. The only known bound is $1.33k$ by Chen et al. [2007 SIAM J. COMPUT.]

**Tags:** ds.algorithms, planar-graphs, parameterized-complexity, vertex-cover, kernelization

> **Comments:**
> **username_1**: As far as I know, the existence of a 2k-vertex kernel for VC was first shown in "Vertex Cover: Further Observations and Further Improvements" from 2001, so it is just over a decade old rather than three; the k^2-vertex kernel by Buss has been known for longer. As for the question whether we can do better on planar graphs: I know that many people have tried, but none have succeeded.  
> **username_0**: If you would like to have a look at Hochbaum's paper (Discrete Applied Mathematics 6 (1983) 243-254), you'll see the 2k kernel there (of coz the name "kernel" was not used).  Actually, your adviser took the same position as me in his survey for IWPEC'09.  
> **username_1**: Thanks - I was not aware of Hochbaum's paper. I agree that the idea of a 2k kernel are there (although the meat of it was already in Nemhauser and Trotter's paper, of course). I don't see it being cited in Bodlaender's IWPEC survey, though.  

---

## 0 answers

