## Abstract

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*(log^{2} *n*log α), or a worst-case update time of O(log^{3} 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* n*log α), amortised, or *O*(log^{2} *n*log α), 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} log^{3}* n*log *ρ*) worst-case, and* O*(ε^{−4} log^{2} 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} 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 variety of problems including maximal matching, ∆ + 1 colouring, and matrix vector multiplication. All update times are worst-case* O(*α + log^{2} *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 ICALP 2014 runs in time O(α^{2} + log^{2} 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*).

Original language | English |
---|---|

Title of host publication | Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |

Publisher | Society for Industrial and Applied Mathematics |

Publication date | 2024 |

Pages | 3062-3088 |

ISBN (Electronic) | 978-1-61197-791-2 |

DOIs | |

Publication status | Published - 2024 |

Event | 2024 Annual ACM-SIAM Symposium on Discrete Algorithms - Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 |

### Conference

Conference | 2024 Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Alexandria |

Period | 07/01/2024 → 10/01/2024 |