We give two fully dynamic algorithms that maintain a $(1+varepsilon)$-approximation of the weight $M$ of the minimum spanning forest of an $n$-node graph $G$ with edges weights in $[1,W]$, for any $varepsilon>0$. (1) Our deterministic algorithm takes $O({W^2 log W}/{varepsilon^3})$ worst-case update time, which is $O(1)$ if both $W$ and $varepsilon$ are constants. Note that there is a lower bound by Patrascu and Demaine (SIAM J. Comput. 2006) shows that it takes $Omega(log n)$ time per operation to maintain the exact weight of the MSF that holds even in the unweighted case, i.e. for $W=1$. We further show that any deterministic data structure that dynamically maintains the $(1+varepsilon)$-approximate weight of the MSF requires super constant time per operation, if $Wgeq (log n)^{omega_n(1)}$. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case $O(frac{1}{varepsilon^4}log^3(frac{1}{varepsilon}))$ update time if $W$ is not too large, more specifically, if $W= O({(m^*)^{1/6}}/{log n})$, where $m^*$ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement this result by showing that for any constant $varepsilon,alpha>0$ and $W=n^{alpha}$, any (randomized) data structure that dynamically maintains the weight of the MSF of a graph $G$ with edge weights in $[1,W]$ and $W = Omega(varepsilon m^*)$ within a multiplicative factor of $(1+varepsilon)$ takes $Omega(log n)$ time per operation.
Download