Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity

Abstract 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 $$ α