Random centres improve constant-round planar graph domination algorithms
Random Centres and the $\varepsilon$-Dependence of Constant-Round Planar Domination
Distributed, Parallel, and Cluster Computing
Summary
Finding the smallest set of nodes that dominate a graph is a common problem in computer science, especially for planar graphs. The authors study faster algorithms that give good approximations to this problem within a limited number of steps or rounds. By using a simple random choice strategy for selecting centers in the graph, they reduce the complexity exponent significantly compared to previous methods. They also analyze how the performance depends on a precision parameter, proving lower bounds on any algorithm’s speed and showing tight round requirements for simpler graph types like paths and forests.
What this means in practice
- •For distributed network engineers: Design faster local algorithms for dominating set problems in planar network topologies using randomized center selection.
- •For graph algorithm developers: Improve approximation efficiency and round complexity in constant-round planar graph domination algorithms by applying random-center clustering.
A theory result. No direct application yet.
Authors
Sebastian Senge
Abstract
It was recently shown (arXiv:2610.09618) that the infimum of the approximation ratios of deterministic constant-round LOCAL algorithms for minimum dominating set on planar graphs is 7. The $(7+\varepsilon)$-approximation given there runs in $T_0+O((c_0/\varepsilon)^κ)$ rounds with $κ=\ln 3/\ln(24/23)\approx 25.81$, and it is asked there whether this exponent can be substantially reduced. We replace the heaviest-edge star selection in its clustering step by a random-centre rule: every part becomes a centre independently with probability $p$, and every non-centre joins its heaviest centre neighbour. For planar graphs this gives $κ<5.89$ with $p=3/8$ (three fair coins per part and level) and $κ<6.7$ with $p=1/2$. An analysis that counts only the join edges cannot go below $5.74$. For every proper minor-closed class of density $a$, the new exponent is never worse, and with about $\frac12\log_2 a$ fair coins per part and level it is smaller by a factor that tends to $8$ as the density grows. This is optimal for the rule when $a$ is an integer and the class contains all $K_{a,n}$. The planar bounds hold verbatim on the torus, the projective plane and the Klein bottle. We then turn to the dependence on $\varepsilon$. On paths, every deterministic $r$-round algorithm for fractional domination, and every randomized one that always outputs a dominating set, has (expected) ratio at least $1+1/(r+4)$. So these approximations need $Ω(1/\varepsilon)$ rounds on every minor-closed class that contains all paths, and on paths this is tight up to an additive constant. On forests and on outerplanar graphs, with no bound on the degree, $O(1/\varepsilon)$ rounds suffice, so there the optimal number of rounds is $Θ(1/\varepsilon)$. The planar level bounds, the bounds on paths and the deterministic bound on forests are machine-checked in Lean 4 with Mathlib.