Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs

Abstract

Given a graph $G=(V,E)$, a ${\hat{I}}^2$-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 ${\hat{I}}^2$. 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 $\hat{I}\text{c◯}(\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 $\tilde{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 $\tilde{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 ${\hat{I}}^2$.