← All papers
First page of Random Centres and the $\varepsilon$-Dependence of Constant-Round Planar Domination

Random Centres and the $\varepsilon$-Dependence of Constant-Round Planar Domination

Sebastian Senge

cs.DC Oct 27, 2026 · v1
Key lemmas, level bounds, exponent estimates and the path lower bound are machine-checked in Lean 4 with Mathlib, in a public repository.
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.

A known (7+ε)-approximation for minimum dominating set on planar graphs, running in a constant number of LOCAL rounds, needs (c0/ε)^κ rounds with κ≈25.81. The open question is whether this exponent can be reduced and what the optimal dependence on ε is.

The heaviest-edge star selection in the clustering step is replaced by a random-centre rule: each part becomes a centre with probability p, and each non-centre joins its heaviest centre neighbour. The expected contracted weight per level is analysed for planar and general minor-closed classes. Lower bounds on paths are proved for deterministic fractional and randomized algorithms. Section 2's lemmas, the level bounds and certificates, the exponent bounds, the path lower bound and the forest upper bound are formalized in Lean 4 with Mathlib.

For planar graphs the exponent drops to κ<5.89 with p=3/8, and an analysis counting only join edges cannot go below 5.74. On paths, r-round algorithms have ratio at least 1+1/(r+4), so Ω(1/ε) rounds are needed, and on forests and outerplanar graphs the optimal number of rounds is Θ(1/ε).

aprior q=1-1/(8a)ours, p=1/2ours, best dyadic pimprovement
18.233.823.822.15×
3 (planar)25.816.976.424.02×
1087.3421.4414.815.89×
100878.34219.18115.677.59×
Exponent κ by density a: prior work versus the random-centre rule