Adaptive Out-Orientations with Applications.

We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that themaximum out-degree is bounded. On one hand, we show how to orient the edges such that maximum out-degree is proportional to the arboricity α of the graph, in, either, an amortised update time of O(log2 n log α),or a worst-case update time of O(log3 n log α). On the other hand, motivated by applications includingdynamic maximal matching, we obtain a different trade-off. Namely, the improved update time of eitherO(log n log α), amortised, or O(log2 n log α), worst-case, for the problem of maintaining an edge-orientationwith at most O(α + log n) out-edges per vertex. Finally, all of our algorithms naturally limit the recourseto be polylogarithmic in n and α. Our algorithms adapt to the current arboricity of the graph, and yieldimprovements over previous work:Firstly, we obtain deterministic algorithms for maintaining a (1 + ε) approximation of the maximumsubgraph density, ρ, of the dynamic graph. Our algorithms have update times of O(ε−6 log3 n log ρ) worst-case, and O(ε−4 log2 n log ρ) amortised, respectively. We may output a subgraph H of the input graph whereits density is a (1 + ε) approximation of the maximum subgraph density in time linear in the size of thesubgraph. These algorithms have improved update time compared to the O(ε−6 log4 n) algorithm by Sawlaniand Wang from STOC 2020.Secondly, we obtain an O(ε−6 log3 n log α) worst-case update time algorithm for maintaining a(1 + ε)OPT + 2 approximation of the optimal out-orientation of a graph with adaptive arboricity α, im-proving the O(ε−6α2 log3 n) algorithm by Christiansen and Rotenberg from ICALP 2022. This yields the firstworst-case polylogarithmic dynamic algorithm for decomposing into O(α) forests.Thirdly, we obtain arboricity-adaptive fully-dynamic deterministic algorithms for a variety of problemsincluding maximal matching, ∆ + 1 colouring, and matrix vector multiplication. All update times are worst-case O(α + log2 n log α), where α is the current arboricity of the graph. For the maximal matching problem,the state-of-the-art deterministic algorithms by Kopelowitz, Krauthgamer, Porat, and Solomon from ICALP2014 runs in time O(α2 + log2 n), and by Neiman and Solomon from STOC 2013 runs in time O(√m). Wegive improved running times whenever the arboricity α ∈ ω(log n√log log n).