English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  The Effect of Girth on the Kernelization Complexity of Connected Dominating Set

Misra, N., Philip, G., Raman, V., & Saurabh, S. (2010). The Effect of Girth on the Kernelization Complexity of Connected Dominating Set. In K. Lodaya, & M. Mahajan (Eds.), 30th International Conference on Foundations of Software Technology and Theoretical Computer Science (pp. 96-107). Wadern: Schloss Dagstuhl. doi:10.4230/LIPIcs.FSTTCS.2010.96.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-D517-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-D51D-0
Genre: Conference Paper

Files

show Files

Locators

show
hide
Locator:
http://drops.dagstuhl.de/opus/volltexte/2010/2856/ (Any fulltext)
Description:
-
OA-Status:

Creators

show
hide
 Creators:
Misra, Neeldhara1, Author
Philip, Geevarghese1, Author           
Raman, Venkatesh1, Author
Saurabh, Saket1, Author
Affiliations:
1External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 20102010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.4230/LIPIcs.FSTTCS.2010.96
BibTex Citekey: MisraPhilipRamanSaurabh2010
URN: urn:nbn:de:0030-drops-28567
 Degree: -

Event

show
hide
Title: 30th International Conference on Foundations of Software Technology and Theoretical Computer Science Science
Place of Event: Chennai, India
Start-/End Date: 2010-12-15 - 2010-12-18

Legal Case

show

Project information

show

Source 1

show
hide
Title: 30th International Conference on Foundations of Software Technology and Theoretical Computer Science
  Abbreviation : FSTTCS 2010
  Subtitle : FSTTCS 2010, December 15–18, 2010, Chennai, India
Source Genre: Proceedings
 Creator(s):
Lodaya, Kamal1, Editor
Mahajan, Meena1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Wadern : Schloss Dagstuhl
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 96 - 107 Identifier: ISBN: 978-3-939897-23-1

Source 2

show
hide
Title: Leibniz International Proceedings in Informatics
  Abbreviation : LIPIcs
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 8 Sequence Number: - Start / End Page: - Identifier: -