We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in @math total time (where the edge weights are from @math ) and explicitly maintains a @math -approximate distance matrix. For a fixed @math , this is the first deterministic partially dynamic algorithm for all-pairs shortest paths in directed graphs, whose update time is @math regardless of the number of edges. Furthermore, we also show how to improve the state-of-the-art partially dynamic randomized algorithms for all-pairs shortest paths [ STOC'02, Bernstein STOC'13] from Monte Carlo randomized to Las Vegas randomized without increasing the running time bounds (with respect to the @math notation). Our results are obtained by giving new algorithms for the problem of dynamically maintaining hubs, that is a set of @math vertices which hit a shortest path between each pair of vertices, provided it has hop-length @math . We give new subquadratic deterministic and Las Vegas algorithms for maintenance of hubs under either edge insertions or deletions.
The dynamic graph problems on digraphs are considerably harder than their counterparts on undirected graphs. An extreme example is the dynamic reachability problem, that is, transitive closure on directed graphs, and connectivity on undirected graphs. While there exist algorithms for undirected graphs with polylogarithmic query and update times @cite_18 @cite_27 @cite_40 @cite_0 @cite_29 , in the case of directed graphs the best known algorithm with polylogarithmic query time has an update time of @math @cite_32 @cite_39 @cite_30 . In addition, a combinatorial algorithm with an update time of @math is ruled out under Boolean matrix multiplication conjecture @cite_16 .
@cite_30 @cite_18 @cite_29 @cite_32 @cite_39 @cite_0 @cite_27 @cite_40 @cite_16
2044040096 2099450374 2283853279 2571471359
This paper presents an efficient fully dynamic graph algorithm for maintaining the transitive closure of a directed graph. The algorithm updates the adjacency matrix of the transitive closure with each update to the graph; hence, each reachability query of the form "Is there a directed path from i to j?" can be answered in O(1) time. The algorithm is randomized and has a one-sided error; it is correct when answering yes, but has O(1 nc) probability of error when answering no, for any constant c. In acyclic graphs, worst case update time is O(n2). In general graphs, the update time is O(n2.26). The space complexity of the algorithm is O(n2). We consider dynamic evaluation of algebraic functions such as computing determinant, matrix adjoint, matrix inverse and solving linear system of equations. We show that in the dynamic setup the above problems can be solved faster than evaluating everything from scratch. In the case when rows and columns of the matrix can change we show an algorithm that achieves O(n sup 2 ) arithmetic operations per update and O(1) arithmetic operations per query. Next, we describe two algorithms, with different tradeoffs, for updating the inverse and determinant when single entries of the matrix are changed. The fastest update for the first tradeoff is O(n sup 1.575 ) arithmetic operations per update and O(n sup 0.575 ) arithmetic operations per query. The second tradeoff gives O(n sup 1.495 ) arithmetic operations per update and O(n sup 1.495 ) arithmetic operations per query. We also consider the case when some number of columns or rows can change. We use dynamic determinant computations to solve the following problems in the dynamic setup: computing the number of spanning trees in a graph and testing if an edge in a graph is contained in some perfect matching. These are the first dynamic algorithms for these problems. Next, with the use of dynamic matrix inverse, we solve fully dynamic transitive closure in general directed graphs. The bounds on arithmetic operations for dynamic matrix inverse translate directly to time bounds for dynamic transitive closure. Thus we obtain the first known algorithm with O(n sup 2 ) worst-case update time and constant query time and two algorithms for transitive closure in general digraphs with subquadratic update and query times. Our algorithms for transitive closure are randomized with one-sided error. We also consider for the first time the case when the edges incident with a part of vertices of the graph can be changed. 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. 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.