Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
share
In a recent breakthrough result, Balliu et al. [FOCS'19] proved a deterministic Ω(min(Δ,log n /loglog n))-round and a randomized Ω(min(Δ,loglog n/logloglog 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 Δ. We provide truly tight bounds in Δ for the complexity of bipartite maximal matching and many natural variants, up to and including the additive constant. As a by-product, our results yield a considerably simplified version of the proof by Balliu et al. We show that our results can be obtained via bounded automatic round elimination, a version of the recent automatic round elimination technique by Brandt [PODC'19] that is particularly suited for automatization from a practical perspective. In this context, our work can be seen as another step towards the automatization of lower bounds in the LOCAL model.
READ FULL TEXT