A fully dynamic reachability algorithm for directed graphs with an almost linear update time

ABSTRACT

We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of O(m+n log n) and a worst-case query time of O(n), where m is the current number of edges in the graph, and n is the number of vertices in the graph. Each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. The algorithm is deterministic and uses fairly simple data structures. This is the first algorithm that breaks the O(n²) update barrier for all graphs with o(n²) edges.One of the ingredients used by this new algorithm may be interesting in its own right. It is a new dynamic algorithm for strong connectivity in directed graphs with an interesting persistency property. Each insert operation creates a new version of the graph. A delete operation deletes edges from emphall versions. Strong connectivity queries can be made on each version of the graph. The algorithm handles each update in O(mα(m,n)) amortized time, and each query in O(1) time, where α(m,n) is a functional inverse of Ackermann's function appearing in the analysis of the union-find data structure. Note that the update time of O(mα(m,n)), in case of a delete operation, is the time needed for updating all versions of the graph.

REFERENCES

• 1: Stephen Alstrup , Cyril Gavoille , Haim Kaplan , Theis Rauhe, Nearest common ancestors: a survey and a new distributed algorithm, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564914]
• 2: Michael A. Bender , Martin Farach-Colton, The LCA Problem Revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.88-94, April 10-14, 2000
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 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: Daniele Frigioni , Tobias Miller , Christos Zaroliagis, An Experimental Study of Dynamic Algorithms for Transitive Closure, Journal of Experimental Algorithmics (JEA), 6, p.9-es, 2001 [doi>10.1145/945394.945403]
• 6: Harold N. Gabow, Path-based depth-first search for strong and biconnected components, Information Processing Letters, v.74 n.3-4, p.107-114, May 2000 [doi>10.1016/S0020-0190(00)00051-X]
• 7: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 8: 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
• 9: Giuseppe F. Italiano, Finding paths and deleting edges in directed acyclic graphs, Information Processing Letters, v.28 n.1, p.5-11, May 30, 1988 [doi>10.1016/0020-0190(88)90136-6]
• 10: 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
• 11: Liam Roditty, A faster and simpler fully dynamic transitive closure, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: Liam Roditty , Uri Zwick, Improved Dynamic Reachability Algorithms for Directed Graphs, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.679, November 16-19, 2002
• 13: Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
• 14: M. Sharir. A strong-connectivity algorithm and its application in data flow analysis. Computers and Mathematics with Applications, 7(1):67--72, 1981.
• 15: R. Tarjan. Depth first search and linear graph algorithms. SIAM Journal on Computing, 11:146--159, 1982.
• 16: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
directed graphs, dynamic graphs algorithms, reachability, transitive closure