Randomized fully dynamic graph algorithms with polylogarithmic time per operation

This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, b ipartiteness, and approximate minimum spanning trees in polylogarithmic tim e per edge insertion or deletion. The algorithms are designed using a new d ynamic technique that combines a novel graph decomposition with randomizati on. They are Las-Vegas type randomized algorithms which use simple data str uctures and have a small constant factor. Let n denote the number of nodes in the graph. For a sequence of Omega(m(0) ) operations, where m(0) is the number of edges in the initial graph, the e xpected time for p updates is O(p log(3) n) (Throughout the paper the logar ithms are base 2.) for connectivity and bipartiteness. The worst-case time for one query is O(log n/log log n). For the k-edge witness problem ("Does the removal of k given edges disconnect the graph?") the expected time for p updates is O(p log(3) n) and the expected time for q queries is O(qk log( 3) n). Given a graph with k different weights, the minimum spanning tree ca n be maintained during a sequence of p updates in expected time O(pk log(3) n). This implies an algorithm to maintain a 1 + epsilon-approximation of t he minimum spanning tree in expected time O((p log(3)n log U)/epsilon) for p updates, where the weights of the edges are between 1 and U.