Distributed maximal matching, greedy is optimal

DOI10.1145/2332432.2332464MaRDI QIDQ2933793zbMATH OpenOpenAlexFDO

Authors Juho Hirvonen, Jukka Suomela

Publication date 5 December 2014

Published in Proceedings of the 2012 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.0367

zbMATH Keywords

distributed algorithmslower boundsmaximal matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

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+lo{g}^{\ast }k)$ rounds, and prior work implies a lower bound of $Omega(polylog(Delta)+lo{g}^{\ast }k)$ rounds. Our work closes the gap between upper and lower bounds: the complexity is $Theta(Delta+lo{g}^{\ast }k)$ rounds. To our knowledge, this is the first linear-in-$Delta$ lower bound for the distributed complexity of a classical graph problem.

Recommendations

• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• Some simple distributed algorithms for sparse networks
• Linear-in- lower bounds in the LOCAL model
• Linear-in- lower bounds in the LOCAL model
• Improved deterministic distributed matching via rounding

Cited in

(8)

• Linear-in- lower bounds in the LOCAL model
• Improved deterministic distributed matching via rounding
• Linear-in- lower bounds in the LOCAL model
• On the Complexity of Distributed Greedy Coloring
• Some simple distributed algorithms for sparse networks
• Distributed half-integral matching and beyond
• Distributed half-integral matching and beyond
• Deterministic local algorithms, unique identifiers, and fractional graph colouring

This page was built for publication: Distributed maximal matching, greedy is optimal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933793)