Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence

Leonid Barenboim and Michael Elkin

Abstract:
We study the edge-coloring problem in the message-passing model of distributed computing. This is one of the most fundamental problems in this area. Currently, the best-known deterministic algorithms for (2∆− 1)-edge-coloring requires O(∆) + log∗ n time [23], where ∆ is the maximum degree of the input graph. Also, recent results of [5] for vertex-coloring imply that one can get an O(∆)-edge-coloring in O(∆^ϵ ·log n) time, and an O(∆^{1+ϵ})-edge-coloring in O(log ∆ log n) time, for an arbitrarily small constant ϵ > 0. In this paper we devise a significantly faster deterministic edge-coloring algorithm. Specifically, our algorithm computes an O(∆)-edge-coloring in O(∆^ϵ ) + log∗ n time, and an O(∆^{1+ϵ} )-edge-coloring in O(log ∆) + log∗ n time. This result improves the state-of-the-art running time for deterministic edge-coloring with this number of colors in almost the entire range of maximum degree ∆. Moreover, it improves it exponentially in a wide range of ∆, specifically, for 2^Ω(log* n) ≤ ∆ ≤ polylog(n). In addition, for small values of ∆ (up to log^{1−δ} n, for some fixed δ > 0) our deterministic algorithm outperforms all the existing randomized algorithms for this problem.

Guest: Leonid Barenboim
Host: Chen Avin