Lower bounds for maximal matchings and maximal independent sets
share
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Δ + ^* n) communication rounds; here n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1992) shows that the dependency on n is optimal: these problems cannot be solved in o(^* 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 maximal matchings and maximal independent sets cannot be found in o(Δ + n / n) rounds. Our lower bound holds for deterministic and randomized distributed algorithms in the LOCAL model of distributed computing.
READ FULL TEXT