Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

ABSTRACT

We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges.(MATH) For the problem of transitive closure, the previous best known algorithms, for achieving O(1) query time, require O(\min(m, \frac{n^3}{m}))$ amortized update time, implying an upper bound of O(n^{\frac{3}{2}})$ on update time per edge-deletion. We present an algorithm that achieves $O(1)$ query time and O(n \log^2n + \frac{n^2}{\sqrt{m}}{\sqrt{\log n}})$ update time per edge-deletion, thus improving the upper bound to O(n^{\frac{4}{3}}\sqrt[3]{\log n})$.(MATH) For the problem of maintaining all-pairs shortest distances in unweighted digraph under deletion of edges, we present an algorithm that requires O(\frac{n^3}{m} \log^2 n)$ amortized update time and answers a distance query in O(1) time. This improves the previous best known update bound by a factor of log n. For maintaining all-pairs shortest paths, we present an algorithm that achieves O(\min(n^{\frac{3}{2}} \sqrt{\log n}, \frac{n^3}{m} \log ^2n))$ amortized update time and reports a shortest path in optimal time (proportional to the length of the path). For the latter problem we improve the worst amortized update time bound by a factor of O(\sqrt{\frac{n}{\log n}})$.(MATH) We also present the first decremental algorithm for maintaining all-pairs (1+&egr;) approximate shortest paths/distances, for any &egr; > 0, that achieves a sub-quadratic update time of O(n log²n + \frac{n^2}{\sqrt{\epsilon m}}\sqrt{\log n})$ and optimal query time.Our algorithms are randomized and have one-sided error for query (with probability O(1/n^c) for any constant c).

REFERENCES

• 1: Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
• 2: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 3: C. Demetrescu. Private communication.
• 4: C. Demetrescu , G. F. Italiano, Fully dynamic transitive closure: breaking through the O(n/sup 2/) barrier, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.381, November 12-14, 2000
• 5: G. Italiano, Fully Dynamic All Pairs Shortest Paths with Real Edge Weights, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.260, October 14-17, 2001
• 6: Donald E. Knuth , Daniel H. Greene, Mathematics for the Analysis of Algorithms, Birkhauser Boston, 1999
• 7: M. R. Henzinger , V. King, Fully dynamic biconnectivity and transitive closure, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.664, October 23-25, 1995
• 8: Valerie King, Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.81, October 17-18, 1999
• 9: Valerie King , Mikkel Thorup, A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms, Proceedings of the 7th Annual International Conference on Computing and Combinatorics, p.268-277, August 20-23, 2001
• 10: J. A. La Poutré , J. van Leeuwen, Maintenance of transitive closures and transitive reductions of graphs, Proceedings of the International Workshop WG '87 on Graph-theoretic concepts in computer science, p.106-120, July 1988, Kloster Banz/Staffelstein, Germany
• 11: Uri Zwick, All Pairs Shortest Paths in weighted directed graphs ? exact and almost exact algorithms, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.310, November 08-11, 1998

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms

Keywords:
BFS tree, decremental, reachability