Randomized fully dynamic graph algorithms with polylogarithmic time per operation

Abstract

This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor. Let n denote the number of nodes in the graph. For a sequence of Ω( m ₀ ) operations, where m ₀ is the number of edges in the initial graph, the expected time for p updates is O ( p log ³ n ) (througout the paper the logarithms are based 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 ³ n ) and the expected time for q queries is O ( qk log ³ n ). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O ( pk log ³ n ). This implies an algorithm to maintain a 1 + ε-approximation of the minimum spanning tree in expected time O (( p log ³ n log U )/ε) for p updates, where the weights of the edges are between 1 and U .