Adaptive Out-Orientations with Applications

We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the edges such that the out-degree of each vertex is proportional to the arboricity α of the graph, in a worst-case update time of O(log 3 n log α). On the other hand, motivated by applications including dynamic maximal matching, we obtain a different trade-off, namely the improved worst case update time of O(log 2 n log α) for the problem of maintaining an edge-orientation with at most O(α + log n) out-edges per vertex. Since our algorithms have update times with worst-case guarantees, the number of changes to the solution (i.e. the recourse) is naturally limited. Our algorithms adapt to the current arboricity of the graph, and yield improvements over previous work:

Firstly, we obtain an O(ε -6 log 3 n log ρ) worst-case update time algorithm for maintaining a (1 + ε) approximation of the maximum subgraph density, ρ, improving upon the O(ε -6 log 4 n) algorithm by Sawlani and Wang from STOC 2020.

Secondly, we obtain an O(ε -6 log 3 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 α, improving the O(ε -6 α 2 log 3 n) algorithm by Christiansen and Rotenberg from ICALP 2022. This yields the first worst-case polylogarithmic dynamic algorithm for decomposing into O(α) forests. Thirdly, we obtain arboricity-adaptive fully-dynamic deterministic algorithms for a varierty, of problems including maximal matching, ∆ + 1 coloring, and matrix vector multiplication. All update times are worst-case O(α + log 2 n log α), where α is the current arboricity of the graph. Specifically for the maximal matching problem, this improves for α ∈ Ω(log n √ log log n), on the deterministic algorithms by Kopelowitz, Krauthgamer, Porat, and Solomon from ICALP 2014 running in time O(α 2 + log 2 n) and by Neiman and Solomon from STOC 2013 running in time O( √ m).