|   | 
Details
   web
Record
Author (up) Kowalik, L.; Pilipczuk, M.; Suchan, K.
Title Towards optimal kernel for connected vertex cover in planar graphs Type
Year 2013 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.
Volume 161 Issue 7-8 Pages 1154-1161
Keywords Kernelization; Planar graphs; Connected vertex cover
Abstract 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 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 question in the 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 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(>= 3) vertices of degree at least 3 contains a matching of cardinality at least n(>= 3)/3. (C) 2012 Elsevier B.V. All rights reserved.
Address Univ Warsaw, Inst Informat, PL-00325 Warsaw, Poland, Email: kowalik@mimuw.edu.pl;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000317451700030 Approved
Call Number UAI @ eduardo.moreno @ Serial 276
Permanent link to this record