Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental problems. Subgraph connectivity asks to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by "on" vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in O (m^ 2 3 ) amortized time, where m denotes the number of edges in the graph. This greatly improves over the previous result [Chan, STOC'02], which required fast matrix multiplication and had an update time of O(m^0.94). The new data structure is also simpler. Geometric connectivity asks to maintain a dynamic set of n geometric objects, and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously, nontrivial fully dynamic results were known only for special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, O (n^ 2 3 ), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear-time range queries, such as arbitrary 2D line segments, d-dimensional simplices, and d-dimensional balls.
If vertices have constant degree, vertex updates are equivalent to edge updates. For edge updates, Henzinger and King @cite_9 were first to obtain polylogarithmic update times (randomized). This was improved by @cite_4 to a deterministic solution with @math time per update, and by Thorup @cite_40 to a randomized solution with @math update time. The randomized bound almost matches the @math lower bound from @cite_24 . All these data structures maintain a spanning forest as a certificate for connectivity. This idea fails for vertex updates in the general case, since the certificate can change substantially after just one update.
@cite_24 @cite_40 @cite_9 @cite_4
1963524245 2010151376 1992869351 2045430818
We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions deletions) in @math amortized time and connectivity queries in @math worst-case time, where @math is the number of vertices of the graph. This improves the deterministic data structures of Holm, de Lichtenberg, and Thorup (STOC 1998, J.ACM 2001) and Thorup (STOC 2000) which both have @math amortized update time and @math worst-case query time. Our model of computation is the same as that of Thorup, i.e., a pointer machine with standard @math instructions. 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. Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph. For the case of a general graph, maintaining the data structure and updating the tree are shown to take @math time, where m is the number of edges in the graph. For the case of a planar graph, a data structure is presented which supports an update time of @math . These structures contribute to improved solutions for the on-line connected components problem and the problem of generating the K smallest spanning trees. 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.