Adaptive Out-Orientations with Applications
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Adaptive Out-Orientations with Applications. / Chekuri, Chandra; Christiansen, Aleksander Bjørn; Holm, Jacob; van der Hoog, Ivor; Quanrud, Kent; Rotenberg, Eva; Schwiegelshohn, Chris.
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2024. p. 3062-3088.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Adaptive Out-Orientations with Applications
AU - Chekuri, Chandra
AU - Christiansen, Aleksander Bjørn
AU - Holm, Jacob
AU - van der Hoog, Ivor
AU - Quanrud, Kent
AU - Rotenberg, Eva
AU - Schwiegelshohn, Chris
N1 - Publisher Copyright: Copyright © 2024 by SIAM.
PY - 2024
Y1 - 2024
N2 - We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the maximum out-degree is bounded. On one hand, we show how to orient the edges such that maximum outdegree is proportional to the arboricity α of the graph, in, either, an amortised update time of O(log2 nlog α), or a worst-case update time of O(log3 nlog α). On the other hand, motivated by applications including dynamic maximal matching, we obtain a different trade-off. Namely, the improved update time of either O(log nlog α), amortised, or O(log2 nlog α), worst-case, for the problem of maintaining an edge-orientation with at most O(α + log n) out-edges per vertex. Finally, all of our algorithms naturally limit the recourse to be polylogarithmic in n and α. Our algorithms adapt to the current arboricity of the graph, and yield improvements over previous work: Firstly, we obtain deterministic algorithms for maintaining a (1 + ε) approximation of the maximum subgraph density, ρ, of the dynamic graph. Our algorithms have update times of O(ε−6 log3 nlog ρ) worst-case, and O(ε−4 log2 nlog ρ) amortised, respectively. We may output a subgraph H of the input graph where its density is a (1 + ε) approximation of the maximum subgraph density in time linear in the size of the subgraph. These algorithms have improved update time compared to the O(ε−6 log4 n) algorithm by Sawlani and Wang from STOC 2020. Secondly, we obtain an O(ε−6 log3 nlog α) 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 log3 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 variety of problems including maximal matching, ∆ + 1 colouring, and matrix vector multiplication. All update times are worst-case O(α + log2 nlog α), 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 ICALP 2014 runs in time O(α2 + log2 n), and by Neiman and Solomon from STOC 2013 runs in time O(√m). We give improved running times whenever the arboricity α ∈ ω(log n√log log n).
AB - We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the maximum out-degree is bounded. On one hand, we show how to orient the edges such that maximum outdegree is proportional to the arboricity α of the graph, in, either, an amortised update time of O(log2 nlog α), or a worst-case update time of O(log3 nlog α). On the other hand, motivated by applications including dynamic maximal matching, we obtain a different trade-off. Namely, the improved update time of either O(log nlog α), amortised, or O(log2 nlog α), worst-case, for the problem of maintaining an edge-orientation with at most O(α + log n) out-edges per vertex. Finally, all of our algorithms naturally limit the recourse to be polylogarithmic in n and α. Our algorithms adapt to the current arboricity of the graph, and yield improvements over previous work: Firstly, we obtain deterministic algorithms for maintaining a (1 + ε) approximation of the maximum subgraph density, ρ, of the dynamic graph. Our algorithms have update times of O(ε−6 log3 nlog ρ) worst-case, and O(ε−4 log2 nlog ρ) amortised, respectively. We may output a subgraph H of the input graph where its density is a (1 + ε) approximation of the maximum subgraph density in time linear in the size of the subgraph. These algorithms have improved update time compared to the O(ε−6 log4 n) algorithm by Sawlani and Wang from STOC 2020. Secondly, we obtain an O(ε−6 log3 nlog α) 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 log3 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 variety of problems including maximal matching, ∆ + 1 colouring, and matrix vector multiplication. All update times are worst-case O(α + log2 nlog α), 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 ICALP 2014 runs in time O(α2 + log2 n), and by Neiman and Solomon from STOC 2013 runs in time O(√m). We give improved running times whenever the arboricity α ∈ ω(log n√log log n).
U2 - 10.1137/1.9781611977912.110
DO - 10.1137/1.9781611977912.110
M3 - Article in proceedings
AN - SCOPUS:85186221629
SP - 3062
EP - 3088
BT - Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
PB - SIAM
T2 - 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Y2 - 7 January 2024 through 10 January 2024
ER -
ID: 393864835