Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
This work provides efficient distributed algorithms for graph theory problems, with incremental improvements over prior methods in specific graph classes.
The paper tackles the problem of finding distributed ruling sets in trees and high-girth graphs, presenting algorithms that achieve near-optimal round complexities, such as an O(log log n)-round randomized algorithm for 2-ruling sets on trees, almost matching a known lower bound.
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 $β$.