Lower Bounds for Maximal Matchings and Maximal Independent Sets

Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikael Rabie, Jukka Suomela

Research output: Contribution to journalArticleScientificpeer-review

13 Citations (Scopus)

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.
Original languageEnglish
Article number39
Pages (from-to)1-30
Number of pages30
JournalJournal of the ACM
Volume68
Issue number5
DOIs
Publication statusPublished - Oct 2021
MoE publication typeA1 Journal article-refereed

Fingerprint

Dive into the research topics of 'Lower Bounds for Maximal Matchings and Maximal Independent Sets'. Together they form a unique fingerprint.

Cite this