Distributed Maximal Matching: Greedy is Optimal

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 $\mathrm{\Delta }$, it is known that a maximal matching can be found in $O(\mathrm{\Delta }+{\log }^{\ast }k)$ rounds, and prior work implies a lower bound of $\mathrm{\Omega }(\text{polylog}(\mathrm{\Delta })+{\log }^{\ast }k)$ rounds. Our work closes the gap between upper and lower bounds: the complexity is $\Theta(\Delta + \log^* k)$rounds\mathrm{.}Toourknowledge,thisisthefirstlinear-in-$\Delta$ lower bound for the distributed complexity of a classical graph problem.