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 Õ(λ 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 Θ(λ 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 Õ(λ 5.5 √ n) worst-case update time, for graphs with min-cut value at most λ. In particular, this also yields an algorithm for fully dynamic exact mincut with Õ(m 1-1/12 ) amortized update time, improving upon Õ(m 1-1/31 ) [Goranci et al., SODA 2023].

We also give the first fully dynamic algorithm that maintains a (1 + ε)-approximation of the fractional arboricity. Our algorithm is deterministic and has O(α log 6 m/ε 4 ) amortized update time, for graphs with arboricity at most α. We extend these results to a Monte Carlo algorithm with 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.