Maintaining Dynamic Graph Properties Deterministically

In this paper we present deterministic fully dynamic algorithms for maintaining several properties on undirected graphs subject to edge insertions and deletions, in polylogarithmic time per operation. Com- bining techniques from [6, 10], we can maintain a minimum spanning forest of a graph with k different edge weights in O(k log 2 n) amor- tized time per update; maintain an 1+-approximation of the mini- mum spanning forest in O(log 2 n log(U (1 + ))/ log(1 + )) amortized time per update, where edge weights are between 1 and U ; test if a graph is bipartite in O(1) worst-case time, supporting updates in O(log 2 n) amortized time; test if the removal of k given edges discon- nect the graph (k-edge witness problem) in O(k log 2 n) amortized time, supporting updates in O(log 2 n) amortized time; maintain a maximal spanning forest decomposition of order k in O(k log 2 n) amortized time per update. For all these problems, our algorithms match the previ- ous best randomized bounds, and improve substantially over the best deterministic bounds.