An Improved Distributed Algorithm for Maximal Independent Set

DOI10.1137/1.9781611974331.CH20MaRDI QIDQ4575597zbMATH OpenOpenAlexFDO

Authors Mohsen Ghaffari

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

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)

Abstract: The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents an extremely simple randomized algorithm providing a near-optimal local complexity for this problem, which incidentally, when combined with some recent techniques, also leads to a near-optimal global complexity. Classical algorithms of Luby [STOC'85] and Alon, Babai and Itai [JALG'86] provide the global complexity guarantee that, with high probability, all nodes terminate after $O(logn)$ rounds. In contrast, our initial focus is on the local complexity, and our main contribution is to provide a very simple algorithm guaranteeing that each particular node $v$ terminates after $O(logmathsfdeg(v)+log1/epsilon)$ rounds, with probability at least $1-epsilon$. The guarantee holds even if the randomness outside $2$-hops neighborhood of $v$ is determined adversarially. This degree-dependency is optimal, due to a lower bound of Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Interestingly, this local complexity smoothly transitions to a global complexity: by adding techniques of Barenboim, Elkin, Pettie, and Schneider [FOCS'12, arXiv: 1202.1983v3], we get a randomized MIS algorithm with a high probability global complexity of $O(logDelta)+2^{O(sqrtloglogn)}$, where $Delta$ denotes the maximum degree. This improves over the $O(lo{g}^{2}Delta)+2^{O(sqrtloglogn)}$ result of Barenboim et al., and gets close to the $Omega(minlogDelta,sqrtlogn)$ lower bound of Kuhn et al. Corollaries include improved algorithms for MIS in graphs of upper-bounded arboricity, or lower-bounded girth, for Ruling Sets, for MIS in the Local Computation Algorithms (LCA) model, and a faster distributed algorithm for the Lov'asz Local Lemma.

Recommendations

• Improved distributed approximations for maximum independent set
• Distributed approximation of maximum independent set and maximum matching
• A new distributed approximation algorithm for the maximum weight independent set problem
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Brief Announcement: Improved Distributed Approximations for Maximum-Weight Independent Set
• Distributed Reconfiguration of Maximal Independent Sets
• Distributed reconfiguration of maximal independent sets
• A New Parallel Algorithm for the Maximal Independent Set Problem
• Distributed Computing
• A Simple Parallel Algorithm for the Maximal Independent Set Problem

Cited in

(84)

• Feedback from nature, an optimal distributed algorithm for \textsc{Maximal Independent Set} selection
• Component stability in low-space massively parallel computation
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Efficient computation of balanced structures
• On the probe complexity of local computation algorithms
• An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
• Distributed independent sets in interval and segment intersection graphs
• A topological perspective on distributed network algorithms
• The complexity of symmetry breaking in massive graphs
• Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
• Distributed Maximal Independent Set using Small Messages
• Sampling and output estimation in distributed algorithms and LCAs
• Brief announcement: Massively parallel ruling set made deterministic
• Brief announcement: Self-stabilizing MIS computation in the beeping model
• Derandomizing local distributed algorithms under bandwidth restrictions
• Distributed independent sets in interval and segment intersection graphs
• Tight Fault Locality
• Exact distributed sampling
• Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets
• Derandomizing local distributed algorithms under bandwidth restrictions
• Brief announcement: Using read-k inequalities to analyze a distributed MIS algorithm
• The locality of distributed symmetry breaking
• Congested clique algorithms for graph spanners
• MIS on trees
• Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
• Toward more localized local algorithms, removing assumptions concerning global knowledge
• Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Distributed algorithms for the Lovász local lemma and graph coloring
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Using read-k inequalities to analyze a distributed MIS algorithm
• Resource efficient stabilization for local tasks despite unknown capacity links
• Parallel derandomization for coloring
• New techniques and tighter bounds for local computation algorithms
• Improved distributed approximations for maximum independent set
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
• Distributed MIS in O( n) awake complexity
• Distributed (+1)-coloring via ultrafast graph shattering
• On the complexity of local distributed graph problems
• Distributed coloring of hypergraphs
• Self-stabilizing MIS computation in the beeping model
• Optimal dynamic distributed MIS
• Distributed set cover approximation: primal-dual with optimal locality
• \textsc{Maximal Independent Sets} in radio networks
• Locally computing edge orientations
• Local distributed rounding: generalized to MIS, matching, set cover, and beyond
• Variable version Lovász local lemma: a tale of two boundaries
• Distributed MIS in O(log log n) Awake Complexity
• Distributed MIS with Low Energy and Time Complexities
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Optimal Message-Passing with Noisy Beeps
• Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization
• Distributed Computing
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Exponential speedup over locality in \textsf{MPC} with optimal memory
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Distributed MIS via all-to-all communication
• An optimal bit complexity randomized distributed MIS algorithm
• Can we locally compute sparse connected subgraphs?
• \((\Delta+1)\) coloring in the congested clique model
• Distributed Lower Bounds for Ruling Sets
• Super-fast 3-ruling sets
• Distributed reconfiguration of maximal independent sets
• Graph reconstruction in the congested clique
• The message complexity of distributed graph optimization
• Mobile agents on chordal graphs: maximum independent set and beyond
• What can be sampled locally?
• Distributed symmetry breaking on power graphs via sparsification
• Optimal message-passing with noisy beeps
• Rounds vs. communication tradeoffs for maximal independent sets
• A time hierarchy theorem for the LOCAL model
• Computing large independent sets in a single round
• Node and edge averaged complexities of local graph problems
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Improved deterministic distributed matching via rounding
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Improved distributed \(\Delta\)-coloring
• A new distributed approximation algorithm for the maximum weight independent set problem
• Distributed Reconfiguration of Maximal Independent Sets
• Network Decomposition and Distributed Derandomization (Invited Paper)

This page was built for publication: An Improved Distributed Algorithm for Maximal Independent Set

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