We present a deterministic distributed algorithm that computes a (2Δ − 1)-edge-coloring, or even list-edgecoloring, in any n-node graph with maximum degree Δ, in O(log 8 Δ·log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e.g., Open Problem 4 in the Distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2 O( √ log n) by Panconesi and Srinivasan [STOC'92] and O( √ Δ) + O(log * n) by Fraigniaud, Heinrich, and Kosowski [ FOCS'16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2Δ − 1)-edgecoloring to poly(log log n) rounds. The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r -where each hyperedge has at most r vertices -with n nodes and maximum degree Δ, this algorithm computes a maximal matching in O(r 5 log 6+log r Δ · log n) rounds. This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkin's book, a (log Δ/ε) O(log 1/ε)round deterministic algorithm for (1 + ε)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting λ-arboricity graphs with out-degree at most (1 + ε)λ , for any constant ε > 0, hence partially answering Open Problem 10 of Barenboim and Elkin's book. √ log n) , due to Panconesi and Srinivasan [PS92]. Panconesi and Rizzi pointed out in the year 2001 [PR01] that "while maximal matchings can be computed in polylogarithmic time, in n, in the distributed model [HKP98], it is a decade old open problem whether the same running time is achievable for the remaining 3 structures." The status remains the same as of today, after almost two more decades. In particular, for edge-coloring which is our main target, Barenboim and Elkin stated the following problem in their recent Distributed 1 If the latter is not the case, it is enough to try exponentially increasing estimates. 2 In the LOCAL model, messages might be of arbitrary size. A variant of the model where the messages have to be of bounded size is known as the CONGEST model [Pel00]. Our edge-coloring algorithms and our MIS and vertex-coloring algorithms for graphs of bounded neighborhood independence in fact work with small O(log n)-bit-size messages. Though, for the sake of the readability, we avoid explicitly discussing the details of this aspect.
The algorithm of REF gives an O(r 3 )-approximation to HMWM in O(r 2 (log Δ) 6+log r + log * n) rounds.
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
Mathematics Computer Science