Super-fast 3-ruling sets

DOI10.4230/LIPICS.FSTTCS.2012.136zbMATH Open1354.68126arXiv1207.3099OpenAlexW2963197483MaRDI QIDQ2957487FDOQ2957487

Authors: Kishore Kothapalli, Sriram Pemmaraju 

Publication date: 26 January 2017

Abstract: A $t$-ruling set of a graph $G=(V,E)$ is a vertex-subset $SsubseteqV$ that is independent and satisfies the property that every vertex $vinV$ is at a distance of at most $t$ from some vertex in $S$. A extit{maximal independent set (MIS)} is a 1-ruling set. The problem of computing an MIS on a network is a fundamental problem in distributed algorithms and the fastest algorithm for this problem is the $O(logn)$-round algorithm due to Luby (SICOMP 1986) and Alon et al. (J. Algorithms 1986) from more than 25 years ago. Since then the problem has resisted all efforts to yield to a sub-logarithmic algorithm. There has been recent progress on this problem, most importantly an $O(logDeltacdotsqrtlogn)$-round algorithm on graphs with $n$ vertices and maximum degree $Delta$, due to Barenboim et al. (Barenboim, Elkin, Pettie, and Schneider, April 2012, arxiv 1202.1983; to appear FOCS 2012). We approach the MIS problem from a different angle and ask if O(1)-ruling sets can be computed much more efficiently than an MIS? As an answer to this question, we show how to compute a 2-ruling set of an $n$-vertex graph in $O((logn{)}^{3/4})$ rounds. We also show that the above result can be improved for special classes of graphs such as graphs with high girth, trees, and graphs of bounded arboricity. Our main technique involves randomized sparsification that rapidly reduces the graph degree while ensuring that every deleted vertex is close to some vertex that remains. This technique may have further applications in other contexts, e.g., in designing sub-logarithmic distributed approximation algorithms. Our results raise intriguing questions about how quickly an MIS (or 1-ruling sets) can be computed, given that 2-ruling sets can be computed in sub-logarithmic rounds.

Full work available at URL: https://arxiv.org/abs/1207.3099

Recommendations

• An Improved Distributed Algorithm for Maximal Independent Set
• Deterministic distributed ruling sets of line graphs
• Distributed Maximal Independent Set using Small Messages
• Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
• The locality of distributed symmetry breaking

zbMATH Keywords

distributed algorithmsmaximal independent setruling setsgraph sparsification

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Cited In (12)

• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
• Lessons from the congested clique applied to MapReduce
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Blazing fast OT for three-round UC OT extension
• Distributed Lower Bounds for Ruling Sets
• Distributed reconfiguration of maximal independent sets
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Distributed Reconfiguration of Maximal Independent Sets
• Deterministic distributed ruling sets of line graphs
• Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets

This page was built for publication: Super-fast 3-ruling sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957487)