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

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 faster parallel batch-dynamic algorithms for maintaining a low out-degree orientation of an undirected graph. All results herein achieve polylogarithmic depth, with high probability (whp); the focus of this paper is on minimizing the work, which varies across results.

Our first result is the first parallel batch-dynamic algorithm to maintain an asymptotically optimal orientation with asymptotically optimal expected work bounds, in an amortized sense, matching the sequential amortized work of Brodal and Fagerberg ~[WADS~'99], albeit in expectation.

Our second result is a $O(c \log n)$ orientation algorithm with expected worst-case $O(\sqrt{\log n})$ work per edge update, where $c$ is a known upper-bound on the arboricity of the graph. This matches, in expectation, the best-known sequential deterministic worst-case $O(c \log n)$ orientation algorithm given by Berglin and Brodal ~[Algorithmica~'18].

Our final result is a $O(c + \log n)$-orientation algorithm with $O(\log^2 n)$ expected worst-case work per edge update, which in the work comes within a O(log n) factor of Berglin and Brodal's sequential $O(c + \log n)$ orientation algorithm.