10.4230/LIPICS.FSTTCS.2009.2315
Dawar, Anuj
Anuj
Dawar
Kreutzer, Stephan
Stephan
Kreutzer
Domination Problems in Nowhere-Dense Classes
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2009
Article
Dominating Set
distance-d dominating set
nowhere-dense graph classes
H-minor free graphs
fixed-parameter tractablility
Kannan, Ravi
Ravi
Kannan
Kumar, K. Narayan
K. Narayan
Kumar
2009
2009-12-14
2009-12-14
2009-12-14
en
urn:nbn:de:0030-drops-23153
10.4230/LIPIcs.FSTTCS.2009
978-3-939897-13-2
1868-8969
10.4230/LIPIcs.FSTTCS.2009
LIPIcs, Volume 4, FSTTCS 2009
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
4
14
157
168
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Kannan, Ravi
Ravi
Kannan
Kumar, K. Narayan
K. Narayan
Kumar
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2009
4
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
231336 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
We investigate the parameterized complexity of generalisations and variations
of 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.
LIPIcs, Vol. 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 157-168