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).