2025/04/17 by Jakob, Manuel, Maus, Yannic, Schager, Florian · 2 citations
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2504.13003
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(log∗(n)) rounds on constant-degree graphs, the seemingly minor reduction to (2Δ-2) colors leads to an Ω(log 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(log 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 Ω(log n) lower bound, whereas the 2Δ-1-edge coloring problem can be solved in O(log∗n) rounds. By plugging in the (2Δ-1)-edge coloring algorithms from [Balliu, Brandt, Kuhn & Olivetti, PODC'22] running in O(log12Δ+ log∗ n) rounds, we obtain an optimal runtime of O(log n) rounds as long as Δ= 2^O(log1/12 n). Furthermore, on general graphs our reduction improves the runtime from \widetildeO(log3 n) to \widetildeO(log5/3 n). In addition, we also obtain an optimal O(log log n)-round randomized reduction of (2Δ- 2)-edge coloring to (2Δ- 1)-edge coloring. Lastly, we obtain an O(logΔn)-round reduction from the (2Δ-1)-edge coloring, albeit to the somewhat harder maximal independent set (MIS) problem.