Constant round approximation for domination in sparse graphs improves algorithms
Almost tight distributed approximation for domination in sparse graph classes
Distributed, Parallel, and Cluster ComputingDiscrete MathematicsData Structures and Algorithms
Summary
Finding a small dominating set in a network means choosing a few nodes so every other node is nearby one of them. The authors developed a new method to quickly find such sets in complex but sparse networks, like certain types of graphs that avoid dense connections. Their method works in a fixed number of steps and gives an answer close to the best possible. This advances previous work by covering more types of sparse networks and answering open questions about the speed and quality of these approximations.
What this means in practice
- •For network engineers: Optimize deployment of monitoring or control points in sparse communication networks using constant-round approximation algorithms for minimal dominating sets.
- •For graph algorithm developers: Implement faster distributed algorithms for dominating set problems on broad classes of sparse graphs, improving applicability beyond minor-free graphs.
Authors
Timothé Picavet
Abstract
We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to bounded expansion. In more detail, for fixed $d$ and $\varepsilon>0$, we give a new deterministic constant-round LOCAL algorithm for Minimum Dominating Set on graphs of maximum average degree at most $d$ and bounded depth-one shallow-minor density. Its approximation ratio is $d+1+\varepsilon$, which is optimal up to $\varepsilon$ for every even integer $d\geq 2$. This improves on the recent results of Amiri and Siebertz by extending beyond proper minor-closed classes. From this algorithm, we derive almost-tight constant-round approximations for a number of graph classes. We get $(7+\varepsilon)$-approximations for planar graphs and graphs of bounded Euler genus, and $(5+\varepsilon)$-approximations for their triangle-free subclasses. This answers the $7+\varepsilon$ question of Wawrzyniak positively, and matches the recent results of Amiri and Siebertz. We also apply our algorithm to classes of bounded queue-number or stack-number, obtaining bounds that are tight up to $\varepsilon$. Additionally, we answer questions of Amiri and Siebertz about improving the dependence of the round complexity on $1/\varepsilon$ and obtaining polynomial local computation for fixed parameters, when comparing the output to the usual domination number.