Distributed maximal matching: greedy is optimal

Conference paper — to appear

Authors: Juho Hirvonen and Jukka Suomela
Title: Distributed maximal matching: greedy is optimal
Conference: 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Madeira, Portugal, July 2012
Links: authors’ version
© 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.
presentation at the Weizmann Institute of Science, 27 November 2011
conference · arXiv.org
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 ∆, 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.
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.