We present an exact fully-dynamic minimum cut algorithm that runs in $n^{o(1)}$ deterministic update time when the minimum cut size is at most $2^{Θ(\log^{3/4-c}n)}$ for any $c>0$, improving on the previous algorithm of Jin, Sun, and Thorup (SODA 2024) whose minimum cut size limit is $(\log n)^{o(1)}$. Combined with graph sparsification, we obtain the first $(1+ε)$-approximate fully-dynamic minimum cut algorithm on weighted graphs, for any $ε\ge2^{-Θ(\log^{3/4-c}n)}$, in $n^{o(1)}$ randomized update time. Our main technical contribution is a deterministic local minimum cut algorithm, which replaces the randomized LocalKCut procedure from El-Hayek, Henzinger, and Li (SODA 2025).
翻译：我们提出了一种精确的完全动态最小割算法，当最小割规模至多为 $2^{Θ(\log^{3/4-c}n)}$（其中 $c>0$）时，该算法在 $n^{o(1)}$ 的确定性更新时间内运行，改进了 Jin、Sun 和 Thorup（SODA 2024）先前算法中最小割规模限制为 $(\log n)^{o(1)}$ 的结果。结合图稀疏化技术，我们首次在加权图上实现了 $(1+ε)$-近似完全动态最小割算法，对于任意 $ε\ge2^{-Θ(\log^{3/4-c}n)}$，该算法在 $n^{o(1)}$ 的随机化更新时间内运行。我们的主要技术贡献是一种确定性局部最小割算法，它替代了 El-Hayek、Henzinger 和 Li（SODA 2025）中的随机化 LocalKCut 过程。
相关内容
微信扫码咨询专知VIP会员