Metraipolis › archive › dc_9838be97c428
Almost tight distributed approximation for domination in sparse graph classes — arXiv:2610.31203
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.31203
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-25T08:37:34.979Z
- SHA-256 of the archived text
5240b12965ffbeffd50544b4589578b285b9d44725b292a9aaeb8acab1b518d2- Stable URL of this page
https://metraipolis.com/documento/dc_9838be97c428
How to cite
Almost tight distributed approximation for domination in sparse graph classes — arXiv:2610.31203 — arXiv (en), https://arxiv.org/abs/2610.31203 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9838be97c428 (Metraipolis archive dc_9838be97c428, sha256 5240b12965ffbeffd50544b4589578b285b9d44725b292a9aaeb8acab1b518d2)
BibTeX
@misc{dc9838be97c428,
title = {Almost tight distributed approximation for domination in sparse graph classes — arXiv:2610.31203},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.31203},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9838be97c428; sha256 5240b12965ffbeffd50544b4589578b285b9d44725b292a9aaeb8acab1b518d2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.31203. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to bounded expansion. In more detail, for fixed $d$ and $\varepsilon>0$, we give a new deterministic constant-round LOCAL algorithm for Minimum Dominating Set on graphs of maximum average degree at most $d$ and bounded depth-one shallow-minor density. Its approximation ratio is $d+1+\varepsilon$, which is optimal up to $\varepsilon$ for every even integer $d\geq 2$. This improves on the recent results of Amiri and Siebertz by extending beyond proper minor-closed classes. From this algorithm, we derive almost-tight constant-round approximations for a number of graph classes. We get $(7+\varepsilon)$-approximations for planar graphs and graphs of bounded Euler genus, and $(5+\varepsilon)$-approximations for their triangle-free subclasses. This answers the $7+\varepsilon$ question of Wawrzyniak positively, and matches the recent results of Amiri and Siebertz. We also apply our algorithm to classes of bounded queue-number or stack-number, obtaining bounds that are tight up to $\varepsilon$. Additionally, we answer questions of Amiri and Siebertz about improving the dependence of the round complexity on $1/\varepsilon$ and obtaining polynomial local computation for fixed parameters, when comparing the output to the usual domination number. Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno). Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2610.31203 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-25T08:31:42.651Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).