Distributed Lower Bounds for Ruling Sets

Given a graph $G = (V,E)$, an $(α, β)$-ruling set is a subset $S \subseteq V$ such that the distance between any two vertices in $S$ is at least $α$, and the distance between any vertex in $V$ and the closest vertex in $S$ is at most $β$. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a $(2, β)$-ruling set in the LOCAL model, we show the following, where $n$ denotes the number of vertices, $Δ$ the maximum degree, and $c$ is some universal constant independent of $n$ and $Δ$. $\bullet$ Any deterministic algorithm requires $Ω\left(\min \left\{ \frac{\log Δ}{β\log \log Δ} , \log_Δn \right\} \right)$ rounds, for all $β\le c \cdot \min\left\{ \sqrt{\frac{\log Δ}{\log \log Δ}} , \log_Δn \right\}$. By optimizing $Δ$, this implies a deterministic lower bound of $Ω\left(\sqrt{\frac{\log n}{β\log \log n}}\right)$ for all $β\le c \sqrt[3]{\frac{\log n}{\log \log n}}$. $\bullet$ Any randomized algorithm requires $Ω\left(\min \left\{ \frac{\log Δ}{β\log \log Δ} , \log_Δ\log n \right\} \right)$ rounds, for all $β\le c \cdot \min\left\{ \sqrt{\frac{\log Δ}{\log \log Δ}} , \log_Δ\log n \right\}$. By optimizing $Δ$, this implies a randomized lower bound of $Ω\left(\sqrt{\frac{\log \log n}{β\log \log \log n}}\right)$ for all $β\le c \sqrt[3]{\frac{\log \log n}{\log \log \log n}}$. For $β> 1$, this improves on the previously best lower bound of $Ω(\log^* n)$ rounds that follows from the 30-year-old bounds of Linial [FOCS'87] and Naor [J.Disc.Math.'91]. For $β= 1$, i.e., for the problem of computing a maximal independent set, our results improve on the previously best lower bound of $Ω(\log^* n)$ on trees, as our bounds already hold on trees.