Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2315
URN: urn:nbn:de:0030-drops-23153
URL: https://drops.dagstuhl.de/opus/volltexte/2009/2315/
Dawar, Anuj ; Kreutzer, Stephan
Domination Problems in Nowhere-Dense Classes
| pdf-format: |
|
Abstract
We investigate the parameterized complexity of generalisations and variationsof the dominating set problem on classes of graphs that are nowhere dense. In
particular, we show that the distance-$d$ dominating-set problem, also known
as the $(k,d)$-centres problem, is fixed-parameter tractable on any class that
is nowhere dense and closed under induced subgraphs. This generalises known
results about the dominating set problem on $H$-minor free classes, classes
with locally excluded minors and classes of graphs of bounded expansion. A
key feature of our proof is that it is based simply on the fact that these
graph classes are uniformly quasi-wide, and does not rely on a structural
decomposition. Our result also establishes that the distance-$d$
dominating-set problem is FPT on classes of bounded expansion, answering a
question of Ne{\v s}et{\v r}il and Ossona de Mendez.
BibTeX - Entry
@InProceedings{dawar_et_al:LIPIcs:2009:2315,
author = {Anuj Dawar and Stephan Kreutzer},
title = {{Domination Problems in Nowhere-Dense Classes}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {157--168},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-13-2},
ISSN = {1868-8969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2315},
URN = {urn:nbn:de:0030-drops-23153},
doi = {10.4230/LIPIcs.FSTTCS.2009.2315},
annote = {Keywords: Dominating Set, distance-d dominating set, nowhere-dense graph classes, H-minor free graphs, fixed-parameter tractablility}
}
| Keywords: | Dominating Set, distance-d dominating set, nowhere-dense graph classes, H-minor free graphs, fixed-parameter tractablility | |
| Seminar: | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science | |
| Issue date: | 2009 | |
| Date of publication: | 14.12.2009 |
