Abstract
Tree-packing is a collection of spanning trees of a graph, serving as a useful tool for computing the minimum cut in static, dynamic, and distributed settings. Notably, [Thorup, Comb. 2007] utilized them to develop a dynamic min-cut algorithm with a worst-case update time of $\tilde O(\lambda^{14.5}\sqrt{n})$.
We reevaluate this relationship, demonstrating that fewer spanning trees are needed to achieve such results; specifically, we show that packing $\Theta(\lambda^3 \log m)$ greedy trees suffices to guarantee a 1-respecting cut or a trivial cut in some contracted graph.
Based on this structural finding, we present a deterministic algorithm for fully dynamic exact min-cut, achieving a worst-case update time of $\tilde O(\lambda^{5.5}\sqrt{n})$ for min-cut values bounded by $\lambda$.
This also leads to a general fully dynamic exact min-cut algorithm with an amortized update time of $\tilde O(m^{1-1/12})$, improving upon $\tilde O(m^{1-1/31})$ from [Goranci et al., SODA 2023]. Furthermore, we introduce the first fully dynamic algorithm maintaining a $(1+\varepsilon)$-approximation of the fractional arboricity, which is strictly harder than the integral arboricity. Our algorithm is deterministic and has an amortized update time of $O(\alpha \log^6 m/\varepsilon^4)$ for arboricity at most $\alpha$.
We extend these results to a Monte Carlo algorithm with an amortized update time of $O(\text{poly}(\log m,\varepsilon^{-1}))$ against an adaptive adversary. Our algorithms also apply to multigraphs. Both results stem from exploring the connection between min-cut/arboricity and (greedy) tree-packing. We investigate tree-packing in a broader sense, including a lower bound for greedy tree-packing, marking the first progress on this topic since [Thorup, Comb. 2007].
Blogger's Review: This research significantly enhances the efficiency of dynamic min-cut algorithms by reducing the number of required spanning trees, and achieves the first dynamic approximation maintenance for fractional arboricity, showcasing the profound impact of tree-packing in graph theory.