Fast Deterministic Distributed Degree Splitting

Abstract

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}({\epsilon }^{-1}\cdot \log n)$ for computing a balanced orientation with discrepancy at most $\epsilon \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}({\epsilon }^{-1}\cdot \log {\epsilon }^{-1}\cdot (\log \log {\epsilon }^{-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+\epsilon )\Delta$-edge coloring can now be solved in $\mathcal{O}({\epsilon }^{-1}\cdot {\log }^2\Delta \cdot \log n+{\epsilon }^{-2}\cdot \log n)$ rounds in LOCAL. Note that for constant $\epsilon$ and $\Delta =\mathcal{O}(2^{{\log }^{1/3}n})$ this runtime matches the current state-of-the-art for $(2\Delta -1)$-edge coloring in [Ghaffari & Kuhn, FOCS'21].

Full version of the article appearing in the proceedings of DISC'26