Distributed Lower Bounds for Ruling Sets

Abstract

Given a graph G=(V, E), an ( α, β )-ruling set is a subset S⊆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 (and hence also any ( α, β )-ruling set with α>2 ) in the LOCAL model of distributed computing, we show the following, where n denotes the number of vertices, Δ the maximum degree, and c is some universal constant independent of NAND Δ . •Any deterministic algorithm requires Ω(min{logΔβloglogΔ, logΔn})rounds, for all β≤cmin{logΔloglogΔ-√, logΔn} . By optimizing Δ, this impliesa deterministic lower bound of Ω(lognβloglogn-√) for all β≤clognloglogn-√3 . •Any randomized algorithm requires Ω(min{logΔβloglogΔ, logΔlogn}) rounds, for allβ≤cmin{logΔloglogΔ-√, logΔlogn} . By optimizing Δ, this implies a randomized lower bound of Ω(loglognβlogloglogn-?√) for all β≤cloglognlogloglogn √3 . 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] (resp. Ω(1) rounds ifβ∈ω(log?n) ). For β=1, i.e. for the problem of computing a maximal independent set (which is nothing else than a (2, 1)-ruling set), our results improve on the previously best lower bound of Ω(log?n) on trees, as our bounds already hold on trees.