Search papers, labs, and topics across Lattice.
This paper introduces the first deterministic algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model, achieving a runtime of $\tilde{O}(\log^5 n)$, which is efficient given the constraints of message size. The algorithm builds on recent advancements in edge coloring from the LOCAL model, addressing the challenge of large message sizes that previous works encountered. By matching the best-known runtime dependency in the LOCAL model, this work significantly advances the understanding of edge coloring in distributed computing environments with limited communication bandwidth.
The first deterministic algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model achieves a runtime that rivals the best in the LOCAL model, despite stringent message size constraints.
Vizing's theorem states that any graph of maximum degree $\Delta$ can be properly edge-colored with $\Delta + 1$ colors (which is optimal in general). A recent breakthrough result by Bernshteyn showed that such a $(\Delta + 1)$-edge coloring can be found deterministically in $poly(\Delta,\log n)$ rounds in the LOCAL model of distributed computing, where $n$ denotes the number of vertices of the input graph [J. Comb. Theory 2022]. Since then, the exponent in the $poly(\log n)$-part of the runtime has been improved by Christiansen [STOC 2023] and Bernshteyn and Dhawan [J. Comb. Theory, Series B, 2025]. However, the algorithms used in all of these works use large messages, leaving open the question for efficient algorithms in the more restrictive CONGEST model. We answer this question by presenting the first $poly(\Delta,\log n)$-round algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model. Our algorithm is deterministic and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.
