Fast Deterministic Distributed Degree Splitting
This provides faster algorithms for distributed graph problems, with applications in edge coloring, but is incremental as it builds on existing methods.
The paper tackles the problem of computing balanced orientations and degree splits in the LOCAL model, achieving an algorithm with complexity O(ε⁻¹·log n) for discrepancy at most ε·deg(v), improving upon prior work. It applies this to edge coloring, solving (3/2+ε)Δ-edge coloring in O(ε⁻¹·log²Δ·log n + ε⁻²·log n) rounds, matching state-of-the-art for certain parameters.
We obtain better algorithms for computing more balanced orientations and degree splits in LOCAL. Important to our result is a connection to the hypergraph sinkless orientation problem [BMNSU, SODA'25] We design an algorithm of complexity $\mathcal{O}(\varepsilon^{-1} \cdot \log n)$ for computing a balanced orientation with discrepancy at most $\varepsilon \cdot \mathrm{deg}(v)$ for every vertex $v \in V$. This improves upon a previous result by [GHKMSU, Distrib. Comput. 2020] of complexity $\mathcal{O}(\varepsilon^{-1} \cdot \log \varepsilon^{-1} \cdot (\log \log \varepsilon^{-1})^{1.71} \cdot \log n)$. Further, we show that this result can also be extended to compute undirected degree splits with the same discrepancy and in the same runtime. As as application we show that $(3 / 2 + \varepsilon)Î$-edge coloring can now be solved in $\mathcal{O}(\varepsilon^{-1} \cdot \log^2 Î\cdot \log n + \varepsilon^{-2} \cdot \log n)$ rounds in LOCAL. Note that for constant $\varepsilon$ and $Î= \mathcal{O}(2^{\log^{1/3} n})$ this runtime matches the current state-of-the-art for $(2Î- 1)$-edge coloring in [Ghaffari & Kuhn, FOCS'21].