On distance r-dominating and 2r-independent sets in sparse graphs

2017/10/27 by Zdenĕk Dvořák, Dvořák, Zdeněk
Computer Science · Economics, Econometrics and Finance · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems

paper · pdf · doi:10.48550/arxiv.1710.10010

openalex publication_date 2017/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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).

Citations

• Approximation algorithms for NP-complete problems on planar graphs

Related

• Constant-factor approximation of domination number in sparse graphs
• Domination above r-independence: does sparseness help?
• Distributed Distance-r Dominating Set on Sparse High-Girth Graphs
• Distributed Domination on Graph Classes of Bounded Expansion
• Kernelization and approximation of distance-r independent sets on\n nowhere dense graphs