toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author (up) Kowalik, L.; Pilipczuk, M.; Suchan, K. pdf  doi
  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:;  
  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
Select All    Deselect All
 |   | 

Save Citations:
Export Records: