Tootfinder

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
Marthe Bonamy, Cyril Gavoille, Timoth\'e Picavet, Alexandra Wesolek
https://arxiv.org/abs/2507.04960

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
We give a new, short proof that graphs embeddable in a given Euler genus-$g$ surface admit a simple $f(g)$-round $α$-approximation distributed algorithm for Minimum Dominating Set (MDS), where the approximation ratio $α\le 906$. Using tricks from Heydt et al. [European Journal of Combinatorics (2025)], we in fact derive that $α\le 34 +\varepsilon$, therefore improving upon the current state of the art of $24g+O(1)$ due to Amiri et al. [ACM Transactions on Algorithms (2019)]. It also improves…