2011/10/10 by Łukasz Kowalik, Marcin Pilipczuk, Kowalik, Lukasz +3 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1110.1964
openalex publication_date 2011/10/10 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
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.