Towards Optimal Distributed Edge Coloring with Fewer Colors

There is a huge difference in techniques and runtimes of distributed algorithms for problems that can be solved by a sequential greedy algorithm and those that cannot. A prime example of this contrast appears in the edge coloring problem: while (2-1) -edge coloring can be solved in O (^ (n) ) rounds on constant-degree graphs, the seemingly minor reduction to (2-2) colors leads to an (n) lower bound Chang, He, Li, Pettie & Uitto, SODA'18. Understanding this sharp divide between very local problems and inherently more global ones remains a central open question in distributed computing and it is a core focus of this paper. As our main contribution we design a deterministic distributed O (n) -round reduction from the (2-2) -edge coloring problem to the much easier (2-1) -edge coloring problem. This reduction is optimal, as the (2-2) -edge coloring problem admits an (n) lower bound, whereas the 2-1-edge coloring problem can be solved in O (^n) rounds. By plugging in the (2-1) -edge coloring algorithms from Balliu, Brandt, Kuhn & Olivetti, PODC'22 running in O (^12 + ^ n) rounds, we obtain an optimal runtime of O (n) rounds as long as = 2^O (^{1/12 n) }. Furthermore, on general graphs our reduction improves the runtime from O (³ n) to O (^5/3 n). In addition, we also obtain an optimal O (n) -round randomized reduction of (2 - 2) -edge coloring to (2 - 1) -edge coloring. Lastly, we obtain an O (_ n) -round reduction from the (2-1) -edge coloring, albeit to the somewhat harder maximal independent set (MIS) problem.