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.FSTTCS.2010.96
URN: urn:nbn:de:0030-drops-28567
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2856/
Misra, Neeldhara ;
Philip, Geevarghese ;
Raman, Venkatesh ;
Saurabh, Saket
The effect of girth on the kernelization complexity of Connected Dominating Set
Abstract
In the Connected Dominating Set problem we are given as input a graph $G$ and a positive integer $k$, and are asked if there is a set $S$ of at most $k$ vertices of $G$ such that $S$ is a dominating set of $G$ and the subgraph induced by $S$ is connected. This is a basic connectivity problem that is known to be NP-complete, and it has been extensively studied using several algorithmic approaches. In this paper we study the effect of excluding short cycles, as a subgraph, on the kernelization complexity of Connected Dominating Set.
Kernelization algorithms are polynomial-time algorithms that take an input and a positive integer $k$ (the parameter) and output an equivalent instance where the size of the new instance and the new parameter are both bounded by some function $g(k)$. The new instance is called a $g(k)$ kernel for the problem. If $g(k)$ is a polynomial in $k$ then we say that the problem admits polynomial kernels. The girth of a graph $G$ is the length of a shortest cycle in $G$. It turns out that Connected Dominating Set is ``hard'' on graphs with small cycles, and becomes progressively easier as the girth increases. More specifically, we obtain the following interesting trichotomy: Connected Dominating Set (a) does not have a kernel of any size on graphs of girth $3$ or $4$ (since the problem is W[2]-hard); (b) admits a $g(k)$ kernel, where $g(k)$ is $k^{O(k)}$, on graphs of girth $5$ or $6$ but has no polynomial kernel (unless the Polynomial Hierarchy (PH) collapses to the third level) on these graphs; (c) has a cubic ($O(k^3)$) kernel on graphs of girth at least $7$.
While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs.
BibTeX - Entry
@InProceedings{misra_et_al:LIPIcs:2010:2856,
author = {Neeldhara Misra and Geevarghese Philip and Venkatesh Raman and Saket Saurabh},
title = {{The effect of girth on the kernelization complexity of Connected Dominating Set}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
pages = {96--107},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-23-1},
ISSN = {1868-8969},
year = {2010},
volume = {8},
editor = {Kamal Lodaya and Meena Mahajan},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2856},
URN = {urn:nbn:de:0030-drops-28567},
doi = {10.4230/LIPIcs.FSTTCS.2010.96},
annote = {Keywords: Connected Dominating Set, parameterized complexity, kernelization, girth}
}
|
Keywords: |
|
Connected Dominating Set, parameterized complexity, kernelization, girth |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) |
|
Issue Date: |
|
2010 |
|
Date of publication: |
|
14.12.2010 |
