License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.31
URN: urn:nbn:de:0030-drops-57327
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5732/
Drange, Pål Grønås ;
Dregi, Markus ;
Fomin, Fedor V. ;
Kreutzer, Stephan ;
Lokshtanov, Daniel ;
Pilipczuk, Marcin ;
Pilipczuk, Michal ;
Reidl, Felix ;
Sánchez Villaamil, Fernando ;
Saurabh, Saket ;
Siebertz, Sebastian ;
Sikdar, Somnath
Kernelization and Sparseness: the Case of Dominating Set
Abstract
We prove that for every positive integer r and for every graph class G of bounded expansion, the r-DOMINATING SET problem admits a linear kernel on graphs from G. Moreover, in the more general case when G is only assumed to be nowhere dense, we give an almost linear kernel on G for the classic DOMINATING SET problem, i.e., for the case r=1. These results generalize a line of previous research on finding linear kernels for DOMINATING SET and r-DOMINATING SET (Alber et al., JACM 2004, Bodlaender et al., FOCS 2009, Fomin et al., SODA 2010, Fomin et al., SODA 2012, Fomin et al., STACS 2013). However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches.
We complement our findings by showing that for the closely related CONNECTED DOMINATING SET problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on H-topological-minor-free graphs (Fomin et al., STACS 2013). Also, we prove that for any somewhere dense class G, there is some r for which r-DOMINATING SET is W[2]-hard on G. Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of r-DOMINATING SET on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.
BibTeX - Entry
@InProceedings{drange_et_al:LIPIcs:2016:5732,
author = {Pål Gr\onås Drange and Markus Dregi and Fedor V. Fomin and Stephan Kreutzer and Daniel Lokshtanov and Marcin Pilipczuk and Michal Pilipczuk and Felix Reidl and Fernando S{\'a}nchez Villaamil and Saket Saurabh and Sebastian Siebertz and Somnath Sikdar},
title = {{Kernelization and Sparseness: the Case of Dominating Set}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {31:1--31:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-001-9},
ISSN = {1868-8969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5732},
URN = {urn:nbn:de:0030-drops-57327},
doi = {10.4230/LIPIcs.STACS.2016.31},
annote = {Keywords: kernelization, dominating set, bounded expansion, nowhere dense}
}
|
Keywords: |
|
kernelization, dominating set, bounded expansion, nowhere dense |
|
Collection: |
|
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
16.02.2016 |
