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 ∆, it is known that a maximal matching can be found in O(∆ + log* 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 Θ(∆ + log* k) rounds. To our knowledge, this is the first linear-in-∆ lower bound for the distributed complexity of a classical graph problem.
Darek Kowalski and Alessandro Panconesi (Eds.): PODC’12, Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, July 16–18, 2012, Madeira, Portugal, pages 165–174, ACM Press, New York, 2012