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

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}\left({\lambda }^{14.5}\sqrt{n}\right)$ 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}logm)$ 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}\left({\lambda }^{5.5}\sqrt{n}\right)$ 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}\left(m^{1-1/12}\right)$ amortized update time, improving upon $\tilde{O}\left(m^{1-1/31}\right)$ [Goranci et al., SODA 2023]. We also give the first fully dynamic algorithm that maintains a $(1+\epsilon )$ -approximation of the fractional arboricity. Our algorithm is deterministic and has $O(\alpha {log}^{6}m/{\epsilon }^4)$ amortized update time, for graphs with arboricity at most $\alpha$ . We extend these results to a Monte Carlo algorithm with $O(poly(logm,{\epsilon }^{-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].