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.]

  • 3
    $\begingroup$ 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. $\endgroup$ Commented Mar 28, 2012 at 18:18
  • 3
    $\begingroup$ 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. $\endgroup$
    – Yixin Cao
    Commented Mar 29, 2012 at 2:59
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 31, 2012 at 2:17


Your Answer

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