| Record |
Author  |
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 |
