Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching

Abstract

We present a deterministic distributed algorithm that computes a $(2\Delta -1)$-edge-coloring, or even list-edge-coloring, in any $n$-node graph with maximum degree $\Delta$, in $O({\log }^7\Delta \log n)$ rounds. This answers one of the long-standing open questions of \emph{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(\sqrt{\log n})}$ by Panconesi and Srinivasan [STOC'92] and $\tilde{O}(\sqrt{\Delta })+O({\log }^{\ast }n)$ by Fraigniaud, Heinrich, and Kosowski [FOCS'16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of $(2\Delta -1)$-edge-coloring to poly$(\log \log n)$ rounds. The key technical ingredient is a deterministic distributed algorithm for \emph{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 $\Delta$, this algorithm computes a maximal matching in $O(r^5{\log }^{6+\log r}\Delta \log n)$ rounds. This hypergraph matching algorithm and its extensions lead to a number of other results. In particular, a polylogarithmic-time deterministic distributed maximal independent set algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkin's book, a $((\log \Delta /\epsilon {)}^{O(\log (1/\epsilon ))})$-round deterministic algorithm for $(1+\epsilon )$-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting $\lambda$-arboricity graphs with out-degree at most $(1+\epsilon )\lambda$, for any constant $\epsilon >0$, hence partially answering Open Problem 10 of Barenboim and Elkin's book.