Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908932201512960 |
|---|---|
| author | Baumecker, Malte Maus, Yannic Uitto, Jara |
| author_facet | Baumecker, Malte Maus, Yannic Uitto, Jara |
| contents | Given a graph $G=(V,E)$, a $β$-ruling set is a subset $S\subseteq V$ that is i) independent, and ii) every node $v\in V$ has a node of $S$ within distance $β$. In this paper we present almost optimal distributed algorithms for finding ruling sets in trees and high girth graphs in the classic LOCAL model. As our first contribution we present an $O(\log\log n)$-round randomized algorithm for computing $2$-ruling sets on trees, almost matching the $Ω(\log\log n/\log\log\log n)$ lower bound given by Balliu et al. [FOCS'20]. Second, we show that $2$-ruling sets can be solved in $\widetilde{O}(\log^{5/3}\log n)$ rounds in high-girth graphs. Lastly, we show that $O(\log\log\log n)$-ruling sets can be computed in $\widetilde{O}(\log\log n)$ rounds in high-girth graphs matching the lower bound up to triple-log factors. All of these results either improve polynomially or exponentially on the previously best algorithms and use a smaller domination distance $β$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21777 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs Baumecker, Malte Maus, Yannic Uitto, Jara Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Given a graph $G=(V,E)$, a $β$-ruling set is a subset $S\subseteq V$ that is i) independent, and ii) every node $v\in V$ has a node of $S$ within distance $β$. In this paper we present almost optimal distributed algorithms for finding ruling sets in trees and high girth graphs in the classic LOCAL model. As our first contribution we present an $O(\log\log n)$-round randomized algorithm for computing $2$-ruling sets on trees, almost matching the $Ω(\log\log n/\log\log\log n)$ lower bound given by Balliu et al. [FOCS'20]. Second, we show that $2$-ruling sets can be solved in $\widetilde{O}(\log^{5/3}\log n)$ rounds in high-girth graphs. Lastly, we show that $O(\log\log\log n)$-ruling sets can be computed in $\widetilde{O}(\log\log n)$ rounds in high-girth graphs matching the lower bound up to triple-log factors. All of these results either improve polynomially or exponentially on the previously best algorithms and use a smaller domination distance $β$. |
| title | Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2504.21777 |