Lower Bounds for Maximal Matchings and Maximal Independent Sets
Authors:
Open Access
- 31 October 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (5) , 1-30
Abstract
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O ( Δ + log * n ) communication rounds; here, n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: These problems cannot be solved in o (log * n ) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that any algorithm that finds a maximal matching or maximal independent set with probability at least 1-1/ n requires Ω (min { Δ , log log n / log log log n }) rounds in the LOCAL model of distributed computing. As a corollary, it follows that any deterministic algorithm that finds a maximal matching or maximal independent set requires Ω (min { Δ , log n / log log n }) rounds; this is an improvement over prior lower bounds also as a function of n .Keywords
All Related Versions
Funding Information
- Research Council of Finland (285721 and 314888)
- Estate (ANR-16-CE25-0009-03)
This publication has 38 references indexed in Scilit:
- Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) TimeSIAM Journal on Computing, 2014
- On the complexity of distributed graph coloring with local minimality constraintsNetworks, 2009
- Some simple distributed algorithms for sparse networksDistributed Computing, 2001
- On the Distributed Complexity of Computing Maximal MatchingsSIAM Journal on Discrete Mathematics, 2001
- On the Complexity of Distributed Network DecompositionJournal of Algorithms, 1996
- 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 and simple randomized parallel algorithm for maximal matchingInformation Processing Letters, 1986