This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with n vertices and m edges while supporting edge insertions and deletions. We show that one can solve the dynamic MSF problem using @math processors and @math worst-case update time, for a total of @math work. This improves on the work of Ferragina [IPPS 1995] which costs @math worst-case update time and @math work.
Notice that an algorithm for dynamic MSF is also an algorithm for dynamic connectivity. However, often there are faster dynamic connectivity algorithms. For the related dynamic connectivity problem, as mentioned above, the fastest deterministic worst-case time algorithm has an @math worst-case update time @cite_10 . When allowing randomization, Kapron, King, and Mountjoy @cite_7 gave a Monte Carlo randomized structure with update time @math and one-sided error probability @math . The update time was later improved to @math independently by @cite_2 and Wang @cite_8 . When allowing amortization Wulff-Nilsen @cite_19 discovered a data structure with @math amortized update time. Recently, @cite_16 showed that if both randomization and amortization are allowed then dynamic connectivity can be solved in expected @math amortized time. Recently, Nanongkai and Saranurak @cite_11 presented a randomized Las-Vegas algorithm for dynamic MSF with an expected worst-case update time of @math for some constant @math .
@cite_7 @cite_8 @cite_19 @cite_2 @cite_16 @cite_10 @cite_11
2571471359 2283853279 2522910400 2565540516
We present two algorithms for dynamically maintaining a spanning forest of a graph undergoing edge insertions and deletions. Our algorithms guarantee worst-case update time and work against an adaptive adversary, meaning that an edge update can depend on previous outputs of the algorithms. We provide the first polynomial improvement over the long-standing O(√n) bound of [Frederickson STOC'84, Eppstein, Galil, Italiano and Nissenzweig FOCS'92] for such type of algorithms. The previously best improvement was O(√n (loglogn)2 logn) [Kejlberg-Rasmussen, Kopelowitz, Pettie and Thorup ESA'16]. We note however that these bounds were obtained by deterministic algorithms while our algorithms are randomized. Our first algorithm is Monte Carlo and guarantees an O(n0.4+o(1)) worst-case update time, where the o(1) term hides the O(√loglogn logn) factor. Our second algorithm is Las Vegas and guarantee an O(n0.49306) worst-case update time with high probability. Algorithms with better update time either needed to assume that the adversary is oblivious (e.g. [Kapron, King and Mountjoy SODA'13]) or can only guarantee an amortized update time. Our second result answers an open problem by To the best of our knowledge, our algorithms are among a few non-trivial randomized dynamic algorithms that work against adaptive adversaries. The key to our results is a decomposition of graphs into subgraphs that either have high expansion or sparse. This decomposition serves as an interface between recent developments on (static) flow computation and many old ideas in dynamic graph algorithms: On the one hand, we can combine previous dynamic graph techniques to get faster dynamic spanning forest algorithms if such decomposition is given. On the other hand, we can adapt flow-related techniques (e.g. those from [Khandekar, Rao and Vazirani STOC'06], [Peng SODA'16], and [Orecchia and Zhu SODA'14]) to maintain such decomposition. To the best of our knowledge, this is the first time these flow techniques are used in fully dynamic graph algorithms. We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time @math and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (STOC 1983) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM 1997), which had update time @math . All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees. Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a new randomized dynamic connectivity structure with @math amortized expected update time and @math query time, which comes within an @math factor of a lower bound due to and Demaine. The new structure is based on a dynamic connectivity algorithm proposed by Thorup in an extended abstract at STOC 2000, which left out some important details. We give a Las Vegas data structure which maintains a minimum spanning forest in an n-vertex edge-weighted undirected dynamic graph undergoing updates consisting of any mixture of edge insertions and deletions. Each update is supported in O(n1 2 - c) worst-case time w.h.p. where c > 0 is some constant, and this bound also holds in expectation. This is the first data structure achieving an improvement over the O(√n) deterministic worst-case update time of , a bound that has been standing for 25 years. In fact, it was previously not even known how to maintain a spanning forest of an unweighted graph in worst-case time polynomially faster than Θ(√n). Our result is achieved by first giving a reduction from fully-dynamic to decremental minimum spanning forest preserving worst-case update time up to logarithmic factors. Then decremental minimum spanning forest is solved using several novel techniques, one of which involves keeping track of low-conductance cuts in a dynamic graph. An immediate corollary of our result is the first Las Vegas data structure for fully-dynamic connectivity where each update is handled in worst-case time polynomially faster than Θ(√n) w.h.p.; this data structure has O(1) worst-case query time.