Metraipolis › archive › dc_77536621fa6c

Near-Optimal Distributed Domination in Planar Graphs — arXiv:2609.32736

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.32736
License (as archived)
CC0-1.0
Archived
2026-10-07T22:12:22.346Z
SHA-256 of the archived text
64968e3727099cc2b8676135f11ffa29a4aae473c97d73a966d1a4bdf016f963
Stable URL of this page
https://metraipolis.com/documento/dc_77536621fa6c

How to cite

Near-Optimal Distributed Domination in Planar Graphs — arXiv:2609.32736 — arXiv (en), https://arxiv.org/abs/2609.32736 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_77536621fa6c (Metraipolis archive dc_77536621fa6c, sha256 64968e3727099cc2b8676135f11ffa29a4aae473c97d73a966d1a4bdf016f963)
BibTeX
@misc{dc77536621fa6c,
  title = {Near-Optimal Distributed Domination in Planar Graphs — arXiv:2609.32736},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.32736},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_77536621fa6c; sha256 64968e3727099cc2b8676135f11ffa29a4aae473c97d73a966d1a4bdf016f963},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.32736. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We give a deterministic $(8+\varepsilon)$-approximation for minimum dominating set on planar graphs in a constant number of rounds of the LOCAL model, for every $\varepsilon>0$. This improves the previous ratio $11+\varepsilon$ obtained by Heydt et al. The ratio is near-optimal in this model: its leading constant is only one above the known lower bound of $7$. Our result closes three quarters of the previous gap, reducing it from $4$ to $1$. Our main contribution is a sharp structural bound. For any dominating set $D$, assigning each vertex outside $D$ to a neighboring center gives disjoint owner blocks. If $k_x$ counts the other blocks containing a neighbor of $x$, then $\sum_{x\notin D}(k_x-2)^+\le(4|D|-12)^+$, where $z^+=\max\{z,0\}$. The bound holds for every such assignment, and equality holds for arbitrarily large minimum dominating sets. We use this bound in their three-phase framework, with new parameters and the same final linear-programming procedure. The algorithm requires neither a planar embedding nor the graph size, and its round bound depends only on $\varepsilon$. The transfer theorem of Bonamy et al. also gives a deterministic $(25+\varepsilon)$-approximation on graphs of bounded Euler genus, with a round bound depending only on $\varepsilon$ and the genus.

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-29 in cs.DC).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2609.32736 — 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-07T21:53:13.751Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).