Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 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
 URL of the conference: http://www.fsttcs.org/archives/2010/ URL for downloading the paper: 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

 (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},