Improved Sampling with Applications to Dynamic Graph Algorithms

We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms. For the dynamic connectivity problem the previously best randomized algorithm takes expected time $O(\log^3n)$ per update, amortized over $\Omega(m)$ updates. Using the new sampling lemma, we improve its running time to $O(\log^2n)$. There exists a lower bound in the cell probe model for the time per operation of $\Omega(\log n/\log \log n)$ for this problem. Similarly improved running times are achieved for the following dynamic problems: (1) $O(\log^3 n)$ to maintain the bridges in a graph (the 2-edge connectivity problem); (2) $O(k \log^2n)$ to maintain a minimum spanning tree in a graph with $k$ different weights (the $k$-weight minimum spanning tree problem); (3) $O(\log^2n \log U/\epsilon')$ to maintain a spanning tree whose weight is a $(1+\epsilon')$-approximation of the weight of the minimum spanning tree, where $U$ is the maximum weight in the graph (the $(1+\epsilon')$-approximate minimum spanning tree problem); and (4) $O(\log^2 n)$ to test if the graph is bipartite (the bipartiteness-testing problem)