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.
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 .
@cite_8 @cite_1 @cite_0 @cite_2 @cite_5 @cite_16
2034499376 2054910423 2006040238 2116636970
We study the following one-person game against a random graph process: the Player's goal is to @math -colour a random sequence of edges @math of a complete graph on @math vertices, avoiding a monochromatic triangle for as long as possible. The game is over when a monochromatic triangle is created. The online version of the game requires that the Player should colour each edge as it comes, before looking at the next edge.While it is not hard to prove that the expected length of this game is about @math , the proof of the upper bound suggests the following relaxation: instead of colouring online, the random graph is generated in only two rounds, and the Player colours the edges of the first round before the edges of the second round are thrown in. Given the size of the first round, how many edges can there be in the second round for the Player to be likely to win? In the extreme case, when the first round consists of a random graph with @math edges, where @math is a positive constant, we show that the Player can win with high probability only if constantly many edges are generated in the second round. We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with @math colours, by prior work it is known that we can find a proper 3-colouring in @math communication rounds. We close the gap between upper and lower bounds: we show that for infinitely many @math the time complexity is precisely @math communication rounds. 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. A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. In 1980 Hahn conjectured that every properly edge-coloured complete graph @math has a rainbow Hamiltonian path. Although this conjecture turned out to be false, it was widely believed that such a colouring always contains a rainbow cycle of length almost @math . In this paper, improving on several earlier results, we confirm this by proving that every properly edge-coloured @math has a rainbow cycle of length @math . One of the main ingredients of our proof, which is of independent interest, shows that a random subgraph of a properly edge-coloured @math formed by the edges of a random set of colours has a similar edge distribution as a truly random graph with the same edge density. In particular it has very good expansion properties.