Super-fast 3-ruling sets

DOI10.4230/LIPICS.FSTTCS.2012.136MaRDI QIDQ2957487zbMATH OpenOpenAlexFDO

Authors Kishore Kothapalli, Sriram Pemmaraju

Publication date 26 January 2017

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

zbMATH Keywords

distributed algorithmsgraph sparsificationmaximal independent setruling sets

Mathematics Subject Classification ID

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

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.

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

Cited in

(15)

• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Deterministic distributed ruling sets of line graphs
• Blazing fast OT for three-round UC OT extension
• 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
• Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets
• Distributed Lower Bounds for Ruling Sets
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
• Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
• The message complexity of distributed graph optimization
• Distributed symmetry breaking on power graphs via sparsification
• Lessons from the congested clique applied to MapReduce

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)