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

arXiv: https://arxiv.org/abs/2405.09141 · HTML: https://mlsanity.com/paper/2405.09141/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2024.

## Built on by (most cited first, 1 of 1)

- [Matroid Algorithms Under Size-Sensitive Independence Oracles](https://mlsanity.com/paper/2605.00201/) (2026)

## Abstract (arXiv)

A tree-packing is a collection of spanning trees of a graph. It has been a useful tool for computing the minimum cut in static, dynamic, and distributed settings. In particular, [Thorup, Comb. 2007] used them to obtain his dynamic min-cut algorithm with tilde O(λ14.5√n) worst-case update time. We reexamine this relationship, showing that we need to maintain fewer spanning trees for such a result; we show that we only need to pack Theta(λ3 log m) greedy trees to guarantee 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(λ5.5√n) worst-case update time, for min-cut value bounded by λ. In particular, this also leads to an algorithm for general fully dynamic exact min-cut with tilde O(m1-1/12) amortized update time, improving upon tilde O(m1-1/31) [Goranci et al., SODA 2023]. We also give the first fully dynamic algorithm that maintains a (1+varepsilon)-approximation of the fractional arboricity -- which is strictly harder than the integral arboricity. Our algorithm is deterministic and has O(α log6m/varepsilon4) amortized update time, for arboricity at most α. We extend these results to a Monte Carlo algorithm with O(poly(log m,varepsilon-1)) amortized update time against an adaptive adversary. Our algorithms work on multi-graphs as well. Both result are obtained by exploring the connection between the min-cut/arboricity and (greedy) tree-packing. We investigate tree-packing in a broader sense; including 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].