Distributed Lower Bounds for Ruling Sets
Authors:
- 1 November 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 365-376
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 ) 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 n and Δ. · Any deterministic algorithm requires Ω(min{[(logΔ)/(β log log Δ)], log Δ n}) rounds, for all β ≤ c·min{√{[(log Δ)/(log log Δ)]}, log Δ n}. By optimizing Δ, this implies a deterministic lower bound of Ω(√{[log n/(β log log n)]}) for all β ≤ c 3 √{[log n/log log n]}. ·Any randomized algorithm requires Ω(min{[(log Δ)/(β log log Δ)], log log n}) rounds, for all β ≤ c·min{√{[(log Δ)/(log log Δ)]}, log log n}. By optimizing Δ, this implies a randomized lower bound of Ω(√{[log log n/(βlog log log n)]}) for all β ≤ c 3 √{[log log n/log log log n]}. For , 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.Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- Deterministic Distributed Vertex Coloring in Polylogarithmic TimeJournal of the ACM, 2011
- An optimal maximal independent set algorithm for bounded-independence graphsDistributed Computing, 2010
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decompositionDistributed Computing, 2009
- On the Complexity of Distributed Network DecompositionJournal of Algorithms, 1996
- What Can be Computed Locally?SIAM Journal on Computing, 1995
- Locality in Distributed Graph AlgorithmsSIAM Journal on Computing, 1992
- A Lower Bound on Probabilistic Algorithms for Distributive Ring ColoringSIAM Journal on Discrete Mathematics, 1991
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986
- A fast parallel algorithm for the maximal independent set problemJournal of the ACM, 1985