摘要
树打包是图的生成树集合，广泛应用于静态、动态和分布式环境中的最小割计算。特别是 [Thorup, Comb. 2007] 利用树打包提出了动态最小割算法，其最坏情况更新时间为 $\tilde O(\lambda^{14.5}\sqrt{n})$。
我们重新审视这一关系，表明为了实现这样的结果，只需维护更少的生成树。我们发现只需打包 $\Theta(\lambda^3 \log m)$ 个贪心树，即可保证在某些收缩图中得到一个 1-尊重割或平凡割。
基于这一结构性结果，我们提出了一个确定性算法，针对最小割值被限制为 $\lambda$ 的情况，其最坏情况更新时间为 $\tilde O(\lambda^{5.5}\sqrt{n})$。
此外，这也引出了一个通用的完全动态确切最小割算法，具有 $\tilde O(m^{1-1/12})$ 的均摊更新时间，改进了 [Goranci et al., SODA 2023] 中的 $\tilde O(m^{1-1/31})$。我们还首次给出了一个完全动态算法，维护 $(1+\varepsilon)$-近似的分数树度，这比整数树度要困难得多。我们的算法是确定性的，均摊更新时间为 $O(\alpha \log^6 m/\varepsilon^4)$，适用于树度最多为 $\alpha$ 的情况。
我们将这些结果扩展到针对自适应对手的蒙特卡罗算法，其均摊更新时间为 $O(\text{poly}(\log m,\varepsilon^{-1}))$。我们的算法同样适用于多重图。这两个结果通过探索最小割/树度与（贪心）树打包之间的联系而获得。我们还在更广泛的意义上研究了树打包，包括贪心树打包的下界，这是自 [Thorup, Comb. 2007] 以来在该主题上的首次进展。
博主点评： 该研究通过减少所需生成树的数量，显著提升了动态最小割算法的效率，并首次实现了对分数树度的动态近似维护，展示了树打包在图论中的深远影响。