Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
Algorithmica · 2026-06 · 88 (3)
DOI: 10.1007/s00453-026-01394-4 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithmica, online erschienen am 03.06.2026. Verfasst von Tijn de Vos und 1 weiteren Autor:innen. Beteiligte Einrichtung: TU Graz, Graz, Austria. Die Arbeit nennt 59 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: HORIZON EUROPE European Research Council, Austrian Science Fund, Villum Fonden.
Abstract (Originalsprache)
Tree-packings – collections of spanning trees of a graph – are a fundamental tool in the study of minimum cut and related graph parameters. They have played a central role in the design of algorithms across static, dynamic, and distributed settings. In this paper, we study both tree-packings themselves and their structural connections to min-cut and arboricity. Our results lead to faster dynamic algorithms for both problems. For dynamic min-cut, [Thorup, Comb. 2007] used tree-packings to obtain his dynamic min-cut algorithm with $$\tilde{O}(\lambda ^{14.5}\sqrt{n})$$ O ~ ( λ 14.5 n ) worst-case update time. We reexamine this relationship, showing that we need to maintain fewer trees for such a result; we show that we only need to pack $$\Theta (\lambda ^3 \log m)$$ Θ ( λ 3 log m ) greedy trees to guarantee either a 1-respecting cut or a trivial cut in some contracted graph. Based on this structural result, we then provide a deterministic algorithm for fully dynamic exact min-cut that has $$\tilde{O}(\lambda ^{5.5}\sqrt{n})$$ O ~ ( λ 5.5 n ) worst-case update time, for graphs with min-cut value at most $$\lambda $$ λ . In particular, this also yields an algorithm for fully dynamic exact min-cut with $$\tilde{O}(m^{1-1/12})$$ O ~ ( m 1 - 1 / 12 ) amortized update time, improving upon $$\tilde{O}(m^{1-1/31})$$ O ~ ( m 1 - 1 / 31 ) [Goranci et al., SODA 2023]. We also give the first fully dynamic algorithm that maintains a $$(1+\varepsilon )$$ ( 1 + ε ) -approximation of the fractional arboricity. Our algorithm is deterministic and has $$O(\alpha \log ^6m/\varepsilon ^4)$$ O ( α log 6 m / ε 4 ) amortized update time, for graphs with arboricity at most $$\alpha $$ α . We extend these results to a Monte Carlo algorithm with $$O(\operatorname {poly}(\log m,\varepsilon ^{-1}))$$ O ( poly ( log m , ε - 1 ) ) amortized update time against an adaptive adversary. Our algorithms work on multi-graphs as well. Our structural results on tree-packing also include a lower bound for greedy tree-packing, which – to the best of our knowledge – is the first progress on this topic since [Thorup, Comb. 2007].
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- TU Graz, Graz, Austria.
- Technical University of Denmark, Copenhagen, Denmark.
Förderung
- HORIZON EUROPE European Research Council
- Austrian Science Fund
- Villum Fonden
Zitieren
APA
de Vos, T., & Christiansen, A. (2026). Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity. Algorithmica, 88(3). https://doi.org/10.1007/s00453-026-01394-4
Vancouver
de Vos T, Christiansen A. Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity. Algorithmica. 2026;88(3). doi:10.1007/s00453-026-01394-4
BibTeX
@article{deVos2026,
author = {de Vos, Tijn and Christiansen, Aleksander},
title = {Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity},
journal = {Algorithmica},
year = {2026},
volume = {88},
number = {3},
doi = {10.1007/s00453-026-01394-4}
}
EUVIMED