Distributed Maximal Matching: Greedy is Optimal

Abstract

We study distributed algorithms that find a maximal matching in an anonymous, edge-coloured graph. If the edges are properly coloured with $k$ colours, there is a trivial greedy algorithm that finds a maximal matching in $k-1$ synchronous communication rounds. The present work shows that the greedy algorithm is optimal in the general case: any algorithm that finds a maximal matching in anonymous, $k$-edge-coloured graphs requires $k-1$ rounds. If we focus on graphs of maximum degree $\Delta$, it is known that a maximal matching can be found in $O(\Delta +{\log }^{\ast }k)$ rounds, and prior work implies a lower bound of $Ω(\polylog(Δ) + \log^* k)$ rounds. Our work closes the gap between upper and lower bounds: the complexity is $\Theta (\Delta +{\log }^{\ast }k)$ rounds. To our knowledge, this is the first linear-in-$\Delta$ lower bound for the distributed complexity of a classical graph problem.

1+15 pages

References in corpus (1)

• Distributed Maximal Matching: Greedy is Optimal

Cited by in corpus (3)

• Lower Bounds for Local Approximation
• Distributed Maximal Matching: Greedy is Optimal
• Linear-in-$\Delta$ Lower Bounds in the LOCAL Model