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$ – Bart Jansen Mar 28 '12 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 Mar 29 '12 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$ – Bart Jansen Mar 31 '12 at 2:17

Your Answer

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

Browse other questions tagged or ask your own question.