Dominating Set above r-independence is paraNP-complete for r=2 even on apex and bounded-degree graphs, W[2]-hard but FPT on nowhere dense graphs for r=3 with linear kernel on bounded expansion, and equivalent to standard parameterization for r>=4.
On distance r-dominating and 2r-independent sets in sparse graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Dvorak (2013) gave a bound on the minimum size of a distance r dominating set in the terms of the maximum size of a distance 2r independent set and generalized coloring numbers, thus obtaining a constant factor approximation algorithm for the parameters in any class of graphs with bounded expansion. We improve and clarify this dependence using an LP-based argument inspired by the work of Bansal and Umboh (2017).
fields
cs.DS 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Domination above r-independence: does sparseness help?
Dominating Set above r-independence is paraNP-complete for r=2 even on apex and bounded-degree graphs, W[2]-hard but FPT on nowhere dense graphs for r=3 with linear kernel on bounded expansion, and equivalent to standard parameterization for r>=4.