# An Improved Distributed Algorithm for Maximal Independent Set

arXiv: https://arxiv.org/abs/1506.05093 · HTML: https://mlsanity.com/paper/1506.05093/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2015.

## Built on by (most cited first, 4 of 4)

- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)
- [Generalization Ability of Feature-based Performance Prediction Models: A Statistical Analysis across Benchmarks](https://mlsanity.com/paper/2405.12259/) (2024)
- [A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning](https://mlsanity.com/paper/2308.13978/) (2023)
- [A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning](https://mlsanity.com/paper/2311.16277/) (2023)

## Abstract (arXiv)

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(log n) 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(log mathsfdeg(v)+log 1/ε) rounds, with probability at least 1-ε. 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(log Delta) + 2^O(√log log n), where Delta denotes the maximum degree. This improves over the O(log2 Delta) + 2^O(√log log n) result of Barenboim et al., and gets close to the Omega(minlog Delta, √log n) 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.