Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918085310545920 |
|---|---|
| author | Bonamy, Marthe Gavoille, Cyril Picavet, Timothé Wesolek, Alexandra |
| author_facet | Bonamy, Marthe Gavoille, Cyril Picavet, Timothé Wesolek, Alexandra |
| contents | 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 the approximation ratio of $91+\varepsilon$ due to Czygrinow et al. [Theoretical Computer Science (2019)] in the particular case of orientable surfaces.
All our distributed algorithms work in the deterministic LOCAL model. They do not require any preliminary embedding of the graph and only rely on two things: a LOCAL algorithm for MDS on planar graphs with ``uniform'' approximation guarantees and the knowledge that graphs embeddable in bounded Euler genus surfaces have asymptotic dimension $2$.
More generally, our algorithms work in any graph class of bounded asymptotic dimension where ``most vertices'' are locally in a graph class that admits a LOCAL algorithm for MDS with uniform approximation guarantees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04960 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs Bonamy, Marthe Gavoille, Cyril Picavet, Timothé Wesolek, Alexandra Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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 the approximation ratio of $91+\varepsilon$ due to Czygrinow et al. [Theoretical Computer Science (2019)] in the particular case of orientable surfaces. All our distributed algorithms work in the deterministic LOCAL model. They do not require any preliminary embedding of the graph and only rely on two things: a LOCAL algorithm for MDS on planar graphs with ``uniform'' approximation guarantees and the knowledge that graphs embeddable in bounded Euler genus surfaces have asymptotic dimension $2$. More generally, our algorithms work in any graph class of bounded asymptotic dimension where ``most vertices'' are locally in a graph class that admits a LOCAL algorithm for MDS with uniform approximation guarantees. |
| title | Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.04960 |