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: if A is a deterministic distributed algorithm that finds a maximal matching in anonymous, k-edge-coloured graphs, then there is a worst-case input in which the running time of A is at least k1 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.
It is easy to come up with an artificial problem with the complexity of @math , but so far no such tight results are known for classical graph problems such as maximal matchings. The lower-bound result by Kuhn and Wattenhofer @cite_3 comes close, but it only applies to a restricted family of algorithms.
@cite_3
2109368894
Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry-breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes the following: An MIS algorithm running in O(log2D  L 2log n, and comes close to the (flog  log log  lower bound of Kuhn, Moscibroda, and Wattenhofer. A maximal matching algorithm running in O(log  + log 4log n) time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on  is nearly optimal. A ( + 1)-coloring algorithm requiring O(log  + 2o(log log n) time, improving on an O(log  + log n)-time algorithm of Schneider and Wattenhofer. A method for reducing symmetry-breaking problems in low arboricity degeneracy graphs to low-degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an O(log n)-time maximal matching algorithm for graphs with arboricity up to 2log n and an O(log 2 3n)-time MIS algorithm for graphs with arboricity up to 2(log n)1 3. Each of our algorithms is based on a simple but powerful technique for reducing a randomized symmetry-breaking task to a corresponding deterministic one on a poly(log n)-size graph.