text: 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.
  @cite_8: The distributed (Δ + 1)-coloring problem is one of most fundamental and well-studied problems in Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there was a long line of gradually improving algorithms published. The current state-of-the-art running time is O(Δ log Δ + log* n), due to Kuhn and Wattenhofer, PODC'06. Linial (FOCS'87) has proved a lower bound of 1 2 log* n for the problem, and Szegedy and Vishwanathan (STOC'93) provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve running time smaller than Θ(Δ log Δ). We present a deterministic (Δ + 1)-coloring distributed algorithm with running time O(Δ) + 1 2 log* n. We also present a tradeoff between the running time and the number of colors, and devise an O(Δ • t)-coloring algorithm with running time O(Δ t + log* n), for any parameter t, 1
  @cite_1: This paper concerns a number of algorithmic problems on graphs and how they may be solved in a distributed fashion. The computational model is such that each node of the graph is occupied by a processor which has its own ID. Processors are restricted to collecting data from others which are at a distance at most t away from them in t time units, but are otherwise computationally unbounded. This model focuses on the issue of locality in distributed processing, namely, to what extent a global solution to a computational problem can be obtained from locally available data.Three results are proved within this model: • A 3-coloring of an n-cycle requires time @math . This bound is tight, by previous work of Cole and Vishkin. • Any algorithm for coloring the d-regular tree of radius r which runs for time at most @math requires at least @math colors. • In an n-vertex graph of largest degree @math , an @math -coloring may be found in time @math .
  @cite_0: 
  @cite_2: We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most 2Δ-1 colours, and maximal matchings can be computed within O(log* n + Δ) deterministic rounds, where Δ is the maximum degree of the network. We also show how to find maximal independent sets and (Δ + 1)-vertex colourings within O(log* n + Δ2) deterministic rounds. All hidden constants are very small and the algorithms are very simple.
  @cite_5: 
  @cite_16: We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an @math -approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.
summary: For many graph problems, the state-of-the-art algorithms are extremely fast even if the network is very large---provided that @math is small. For example, the following problems can be solved in @math synchronous communication rounds (assuming @math -bit node identifiers): [noitemsep] maximal matching @cite_2 , vertex colouring with @math colours @cite_8 @cite_5 , edge colouring with @math colours @cite_2 . There are also problems that can be solved in @math rounds, independently of @math (even in anonymous networks without unique identifiers): [noitemsep] maximal matching in @math -coloured graphs @cite_0 , maximal edge packing @cite_16 , @math -approximation of minimum vertex cover @cite_16 . For each of these problems, the dependence on @math in the running time is well-understood. In particular, Linial's @cite_1 lower bound shows that maximal matching, vertex colouring, and edge colouring require @math rounds, even if @math .