Random Centres and the -Dependence of Constant-Round Planar Domination
In the authors' words
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 -approximation given there runs in rounds with , 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 , and every non-centre joins its heaviest centre neighbour. For planar graphs this gives with (three fair coins per part and level) and with . An analysis that counts only the join edges cannot go below . For every proper minor-closed class of density , the new exponent is never worse, and with about fair coins per part and level it is smaller by a factor that tends to as the density grows. This is optimal for the rule when is an integer and the class contains all . The planar bounds hold verbatim on the torus, the projective plane and the Klein bottle. We then turn to the dependence on . On paths, every deterministic -round algorithm for fractional domination, and every randomized one that always outputs a dominating set, has (expected) ratio at least . So these approximations need 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, rounds suffice, so there the optimal number of rounds is . The planar level bounds, the bounds on paths and the deterministic bound on forests are machine-checked in Lean 4 with Mathlib.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.