Juho Hirvonen · Jukka Suomela

Distributed maximal matching: greedy is optimal

PODC 2012 · 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Madeira, Portugal, July 2012 · doi:10.1145/2332432.2332464

authors’ version publisher’s version arXiv.org


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

ISBN 978-1-4503-1450-3


© ACM 2012 — This is the authors’ version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proc. 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. http://doi.acm.org/10.1145/2332432.2332464

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.