Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
Sebastian Brandt, Dennis Olivetti · 2020
In a recent breakthrough result, Balliu et al. [FOCS'19] proved a deterministic Ω(min(Δ, log n/ log log n))-round and a randomized Ω(min(Δ, log log n/ log log log n))-round lower bound for the complexity of the bipartite maximal matching problem on n-node graphs in the LOCAL model of distributed computing. Both lower bounds are asymptotically tight as a function of the maximum degree Δ.