MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Misra, Neeldhara
Philip, Geevarghese
Raman, Venkatesh
Saurabh, Saket		dblp
dblp
dblp
dblp
Not MPG Author(s):
Misra, Neeldhara
Raman, Venkatesh
Saurabh, Saket
Editor(s):
Lodaya, Kamal
Mahajan, Meena		dblp
dblp
Not MPII Editor(s):
Lodaya, Kamal
Mahajan, Meena
BibTeX cite key*:
MisraPhilipRamanSaurabh2010
Title, Booktitle
Title*:
The effect of girth on the kernelization complexity of Connected Dominating Set
girthcds.pdf (539.35 KB)
Booktitle*:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India
Event, URLs
Conference URL::
http://www.fsttcs.org/archives/2010/
Downloading URL:
http://drops.dagstuhl.de/opus/volltexte/2010/2856/pdf/10.pdf
Event Address*:
Chennai, India
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
15 December 2010
Event End Date:
18 December 2010
Publisher
Name*:
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
URL:
http://www.dagstuhl.de/
Address*:
Dagstuhl, Germany
Type:
Vol, No, Year, pp.
Series:
Leibniz International Proceedings in Informatics
Volume:
8
Number:
Month:
Pages:
96-107
Year*:
2010
VG Wort Pages:
ISBN/ISSN:
978-3-939897-23-1
Sequence Number:
DOI:
10.4230/LIPIcs.FSTTCS.2010.96
Note, Abstract, ©
(LaTeX) 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 {\em kernelization complexity} of
Connected Dominating Set.

Kernelization algorithms are polynomial-time algorithms that
take an input and a positive integer $k$ (the {\em 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)$ {\em 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

\begin{itemize}
\item does not have a kernel of {\em any} size on graphs of girth
$3$ or $4$ (since the problem is W[2]-hard);
\item admits a $g(k)$ kernel, where $g(k)$ is $k^{O(k)}$, on
graphs of girth $5$ or $6$ but has {\em no} polynomial kernel
(unless the Polynomial Hierarchy (PH) collapses to the third
level) on these graphs;
\item has a cubic ($O(k^3)$) kernel on graphs of girth at least $7$.
\end{itemize}
While there is a large and growing collection of parameterized
complexity results available for problems on graph classes
characterized by excluded {\em minors}, our results add to the
very few known in the field for graph classes characterized by
excluded {\em subgraphs}.
URL for the Abstract:
http://drops.dagstuhl.de/opus/volltexte/2010/2856/
Keywords:
Connected Dominating Set, Parameterized Complexity, Kernelization, Girth
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{MisraPhilipRamanSaurabh2010,
AUTHOR = {Misra, Neeldhara and Philip, Geevarghese and Raman, Venkatesh and Saurabh, Saket},
 EDITOR = {Lodaya, Kamal and Mahajan, Meena},
 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, December 15-18, 2010, Chennai, India},
 PUBLISHER = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
 YEAR = {2010},
 VOLUME = {8},
 PAGES = {96--107},
 SERIES = {Leibniz International Proceedings in Informatics},
 ADDRESS = {Chennai, India},
 ISBN = {978-3-939897-23-1},
 DOI = {10.4230/LIPIcs.FSTTCS.2010.96},
}

Entry last modified by Geevarghese Philip, 07/08/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
04/21/2012 17:48:43
Revision
1.
0.


Editor
Geevarghese Philip
Geevarghese Philip


Edit Date
12/08/2012 04:43:30 AM
04/21/2012 05:48:43 PM


File Attachment Icon
girthcds.pdf