Towards optimal kernel for connected vertex cover in planar graphs

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⊆coNP/poly), for planar graphs Guo and Niedermeier [ICALP’08] showed a kernel with at most 14k14k vertices, subsequently improved by Wang et al. [MFCS’11] to 4k4k. The constant 44 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 question in the negative: we show a 113k-vertex kernel for Connected Vertex Cover in planar graphs. We believe that this result will motivate further study in the search for an optimal kernel.In our analysis, we show an extension of a theorem of Nishizeki and Baybars [Takao Nishizeki, Ilker Baybars, Lower bounds on the cardinality of the maximum matchings of planar graphs, Discrete Mathematics 28 (3) (1979) 255–267] which might be of independent interest: every planar graph with n≥3n≥3 vertices of degree at least 3 contains a matching of cardinality at least n≥3/3n≥3/3.