License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.177
URN: urn:nbn:de:0030-drops-30097
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3009/
Jansen, Bart M. P. ;
Bodlaender, Hans L.
Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter
Abstract
Kernelization is a concept that enables the formal mathematical analysis of data reduction through the framework of parameterized complexity. Intensive research into the Vertex Cover problem has shown that there is a preprocessing algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',k') in polynomial time with the guarantee that G' has at most 2k' vertices (and thus O((k')^2) edges) with k' <= k. Using the terminology of parameterized complexity we say that k-Vertex Cover has a kernel with 2k vertices. There is complexity-theoretic evidence that both 2k vertices and Theta(k^2) edges are optimal for the kernel size. In this paper we consider the Vertex Cover problem with a different parameter, the size fvs(G) of a minimum feedback vertex set for G. This refined parameter is structurally smaller than the parameter k associated to the vertex covering number VC(G) since fvs(G) <= VC(G) and the difference can be arbitrarily large. We give a kernel for Vertex Cover with a number of vertices that is cubic in fvs(G): an instance (G,X,k) of Vertex Cover, where X is a feedback vertex set for G, can be transformed in polynomial time into an equivalent instance (G',X',k') such that k' <= k, |X'| <= |X| and most importantly |V(G')| <= 2k and |V(G')| in O(|X'|^3). A similar result holds when the feedback vertex set X is not given along with the input. In sharp contrast we show that the Weighted Vertex Cover problem does not have polynomial kernel when parameterized by fvs(G) unless the polynomial hierarchy collapses to the third level (PH=Sigma_3^p). Our work is one of the first examples of research in kernelization using a non-standard parameter, and shows that this approach can yield interesting computational insights. To obtain our results we make extensive use of the combinatorial structure of independent sets in forests.
BibTeX - Entry
@InProceedings{jansen_et_al:LIPIcs:2011:3009,
author = {Bart M. P. Jansen and Hans L. Bodlaender},
title = {{Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {177--188},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-25-5},
ISSN = {1868-8969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3009},
URN = {urn:nbn:de:0030-drops-30097},
doi = {10.4230/LIPIcs.STACS.2011.177},
annote = {Keywords: kernelization, lower bounds, parameterized complexity}
}
|
Keywords: |
|
kernelization, lower bounds, parameterized complexity |
|
Collection: |
|
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) |
|
Issue Date: |
|
2011 |
|
Date of publication: |
|
11.03.2011 |
