Distributed Lower Bounds for Ruling Sets

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