Search papers, labs, and topics across Lattice.
This paper presents an improved distributed algorithm for computing balanced orientations and degree splits in the LOCAL model, achieving a runtime of $\mathcal{O}(\varepsilon^{-1} \cdot \log n)$ for discrepancy $\varepsilon \cdot \mathrm{deg}(v)$. The key improvement stems from a connection to the hypergraph sinkless orientation problem, enabling a faster algorithm compared to prior work. As an application, the authors demonstrate a faster $(3 / 2 + \varepsilon)\Delta$-edge coloring algorithm, matching the state-of-the-art for $(2\Delta - 1)$-edge coloring for certain parameter ranges.
Forget slow distributed algorithms: a new approach slashes the time to compute balanced orientations and degree splits by leveraging hypergraph sinkless orientations.
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)\Delta$-edge coloring can now be solved in $\mathcal{O}(\varepsilon^{-1} \cdot \log^2 \Delta \cdot \log n + \varepsilon^{-2} \cdot \log n)$ rounds in LOCAL. Note that for constant $\varepsilon$ 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].
