Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
Manuela Fischer, Mohsen Ghaffari, Fabian Kühn · 2017
We present a deterministic distributed algorithm that computes a (2Δ-1)-edge-coloring, or even list-edge-coloring, in any n-node graph with maximum degree Δ, in O(log8Δ·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 2O(√(log n)by Panconesi and Srinivasan [STOC'92] and Õ(√(Δ)) + 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)-edge-coloring 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(r5log6+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 Elkins 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.