Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest
share
We give two fully dynamic algorithms that maintain a (1+ε)-approximation of the weight M of the minimum spanning forest of an n-node graph G with edges weights in [1,W], for any ε>0. (1) Our deterministic algorithm takes O(W^2 log W/ε^3) worst-case update time, which is O(1) if both W and ε are constants. Note that there is a lower bound by Patrascu and Demaine (SIAM J. Comput. 2006) shows that it takes Ω(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+ε)-approximate weight of the MSF requires super constant time per operation, if W≥ (log n)^ω_n(1). (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case O(1/ε^4log^3(1/ε)) 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 ε,α>0 and W=n^α, any (randomized) data structure that dynamically maintains the weight of the MSF of a graph G with edge weights in [1,W] and W = Ω(ε m^*) within a multiplicative factor of (1+ε) takes Ω(log n) time per operation.
READ FULL TEXT