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 NPcomplete, 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 polynomialtime 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 = {96107},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897231},
ISSN = {18688969},
year = {2010},
volume = {8},
editor = {Kamal Lodaya and Meena Mahajan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2856},
URN = {urn:nbn:de:0030drops28567},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.96},
annote = {Keywords: Connected Dominating Set, parameterized complexity, kernelization, girth}
}
2010
Keywords: 

Connected Dominating Set, parameterized complexity, kernelization, girth 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Issue date: 

2010 
Date of publication: 

2010 