We provide a new constant factor approximation algorithm for the (connected) distance-r dominating set problem on graph classes of bounded expansion. Classes of bounded expansion include many familiar classes of sparse graphs such as planar graphs and graphs with excluded (topological) minors, and notably, these classes form the most general subgraph closed classes of graphs for which a sequential constant factor approximation algorithm for the distance-r dominating set problem is currently known. Our algorithm can be implemented in the CONGEST BC model of distributed computing and uses O(r 2 log n) communication rounds. Our techniques, which may be of independent interest, are based on a distributed computation of sparse neighborhood covers of small radius on bounded expansion classes. We show how to compute an r -neighborhood cover of radius 2r and overlap f (r ) on every class of bounded expansion in O(r 2 log n) communication rounds for some function f . Finally, we show how to use the greater power of the LOCAL model to turn any distance-r dominating set into a constantly larger connected distance-r dominating set in 3r + 1 rounds on any class of bounded expansion. Combining this algorithm, e.g., with the constant factor approximation algorithm for dominating sets on planar graphs of Lenzen et al. gives a constant factor approximation algorithm for connected dominating sets on planar graphs Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. SPAA '18, July 16-18, 2018, Vienna, Austria © 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-5799-9/18/07. . . $15.00 https://doi.org/10. 1145/3210377.3210383 in a constant number of rounds in the LOCAL model, where the approximation ratio is only 6 times larger than that of Lenzen et al. 's algorithm.
That is the only known algorithm that solves the problem on a non-trivial class of graphs (e.g. paths, cliques are among trivial classes of graphs) is the algorithm of Amiri et al. REF for bounded expansion graphs which provides a constant factor approximation in a logarithmic number of rounds.
Distributed Domination on Graph Classes of Bounded Expansion
SPAA '18
Computer Science