Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation

Abstract

A low out-degree orientation directs each edge of an undirected graph with the goal of minimizing the maximum out-degree of a vertex. In the parallel batch-dynamic setting, one can insert or delete batches of edges, and the goal is to process the entire batch in parallel with work per edge similar to that of a single sequential update and with span (or depth) for the entire batch that is polylogarithmic. In this paper we present work-efficient parallel batch-dynamic algorithms for maintaining a low out-degree orientation of an undirected graph, both in the amortized and worst-case settings. All results herein achieve polylogarithmic span; the focus of this paper is on minimizing the work, which varies across results. Both of our algorithms also have deterministic bounds with an additional logarithmic factor in the work. In the amortized setting, we give a parallel batch-dynamic algorithm that maintains a $O(c)$-orientation in $O(\log n)$ work per update in expectation, where $c$ is a known upper bound on the arboricity over the update sequence. This result is the parallelization of the classic dynamic orientation algorithm of Brodal and Fagerberg [WADS '99], and, in this setting, is a logarithmic factor faster than Liu et al. [SPAA '22]. In the worst-case setting, we give an $O(c+\log n)$-orientation with worst-case expected work per update $O(\log n)$. This is work-efficient, matching the best known sequential dynamic work of Berglin and Brodal [Algorithmica '20], and implies the existence of an $O(c)$-orientation algorithm with $O({\log }^{2}n)$ worst-case expected work per update. Our algorithm significantly improves, in the setting where $c$ is a fixed upper bound on arboricity, upon the parallel algorithm of Ghaffari and Koo [SPAA '25], which maintains a $O(c)$-orientation with $O({\log }^{9}n)$ worst-case work per edge with high probability (whp).

55 pages. In this version, we give a new worst-case algorithm with O(log n) work per update, which improves on the O(log^2 n) algorithm of our previous version. Abstract shortened for arXiv requirements