(2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
Michael Elkin, Seth Pettie, Hsin-Hao Su · 2014
Graph coloring is a central problem in distributed computing. Both vertex- and edge-coloring problems have been extensively studied in this context. In this paper we show that a (2Δ — l)-edge-coloring can be computed in time smaller than logε n for any ε > 0, specifically, in rounds. This establishes a separation between the (2Δ — 1)-edge-coloring and Maximal Matching problems, as the latter is known to require time [15]. No such separation is currently known between the (Δ + l)-vertex-coloring and Maximal Independent Set problems. We devise a (1 + ε)Δ-edge-coloring algorithm for an arbitrarily small constant ε > 0. This result applies whenever Δ ≥ Δε, for some constant Δε which depends on e. The running time of this algorithm is . A much earlier logarithmic-time algorithm by Dubhashi, Grable and Panconesi [11] assumed Δ ≥ (log n)1+Ω(1). For Δ = (log n)1+Ω(1) the running time of our algorithm is only O (log* n). This constitutes a drastic improvement of the previous logarithmic bound [11, 9]. Our results for (2Δ — 1)-edge-coloring also follows from our more general results concerning (1 — ε)-locally sparse graphs. Specifically, we devise a (Δ + l)-vertex coloring algorithm for (1 — ε)-locally sparse graphs that runs in O(log* Δ + log(l/ε)) rounds for any ε > 0, provided that ε Δ = (log n)1+Ω(1). We conclude that the (Δ + l)-vertex coloring problem for (1 — ε)-locally sparse graphs can be solved in time. This imply our result about (2Δ — 1)-edge-coloring, because (2Δ — 1)-edge-coloring reduces to (Δ + l)-vertex-coloring of the line graph of the original graph, and because line graphs are (1/2 + o(1))-locally sparse.