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
2045430818 2395489635 2099450374 2102347446 1886894033 2010151376 2146507303
Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O(log2 n) for connectivity, O(log4 n) for minimum spanning forest, 2-edge connectivity, and O(log5 n) biconnectivity. The dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes which is undergoing a sequence of edge insertions and deletions, answer queries of the form q(a, b): "Is there a path between nodes a and b?" While data structures for this problem with polylogarithmic amortized time per operation have been known since the mid-1990's, these data structures have Θ(n) worst case time. In fact, no previously known solution has worst case time per operation which is o(√n). We present a solution with worst case times O(log4 n) per edge insertion, O(log5 n) per edge deletion, and O(log n log log n) per query. The answer to each query is correct if the answer is "yes" and is correct with high probability if the answer is "no". The data structure is based on a simple novel idea which can be used to quickly identify an edge in a cutset. Our technique can be used to simplify and significantly speed up the preprocessing time for the emergency planning problem while matching previous bounds for an update, and to approximate the sizes of cutsets of dynamic graphs in time O(min |S|, |V | ) for an oblivious adversary. 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. 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 V(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is O( p log 3 n) (Throughout the paper the logarithms are base 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 3 n) and the expected time for q queries is O(qk log 3 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 3 n). This implies an algorithm to maintain a 1 1 e-approximation of the minimum spanning tree in expected time O((p log 3 n log U) e) for p updates, where the weights of the edges are between 1 and U. We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions deletions) in O(log2 n log log n) amortized time and connectivity queries in O(log n log log n) worst-case time, where n 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 O(log2 n) amortized update time and O(log n log log n) worst-case query time. Our model of computation is the same as that of Thorup, i.e., a pointer machine with standard AC0 instructions. In this paper we present near-optimal bounds for fullydynamic graph connectivity which is the most basic nontrivial fully-dynamic graph problem. Connectivity queries are supported in O(log n log log log n) time while the updates are supported in O(log n(log log n) 3) expected amortized time. The previous best update time was O((log n)2). Our new bound is only doubly-logarithmic factors from a general cell probe lower bound of f2(log n log log n). Our algorithm runs on a pointer machine, and uses only standard AC ° instructions. In our developments we make some comparatively trivial observations improving some deterministic bounds. The space bound of the previous O((log n) ) connectivity algorithm is improved from O(m + n log n) to O(m). The previous time complexity of fully-dynamic 2-edge and biconnectivity is improved from O((log n) 4) to O((log n) 3 log log n). We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough on one of five major open problems in the theory of algorithms: 1) Is the 3SUM problem on n numbers in O(n2 -- aepsi;) time for some aepsi; > 0? 2) Can one determine the satisfiability of a CNF formula on n variables and poly n clauses in O((2 -- aepsi;)npolyn) time for some aepsi; > 0? 3) Is the All Pairs Shortest Paths problem for graphs on n vertices in O(n3 -- aepsi;) time for some aepsi; > 0? 4) Is there a linear time algorithm that detects whether a given graph contains a triangle? 5) Is there an O(n3 -- aepsi;) time combinatorial algorithm for n × n Boolean matrix multiplication? The problems we consider include dynamic versions of bipartite perfect matching, bipartite maximum weight matching, single source reachability, single source shortest paths, strong connectivity, subgraph connectivity, diameter approximation and some nongraph problems such as Pagh's problem defined in a recent paper by pa#x0103;traa#x015F;cu [STOC 2010].