%0 Journal Article
%T Towards optimal kernel for connected vertex cover in planar graphs
%A Lukasz Kowalik
%A Marcin Pilipczuk
%A Karol Suchan
%J Computer Science
%D 2011
%I arXiv
%X We study the parameterized complexity of the connected version of the vertex cover problem, where the solution set has to induce a connected subgraph. Although this problem does not admit a polynomial kernel for general graphs (unless NP is a subset of coNP/poly), for planar graphs Guo and Niedermeier [ICALP'08] showed a kernel with at most 14k vertices, subsequently improved by Wang et al. [MFCS'11] to 4k. The constant 4 here is so small that a natural question arises: could it be already an optimal value for this problem? In this paper we answer this quesion in negative: we show a (11/3)k-vertex kernel for Connected Vertex Cover in planar graphs. We believe that this result will motivate further study in search for an optimal kernel.
%U http://arxiv.org/abs/1110.1964v1