Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O(n2 barrier

ABSTRACT

We present an algorithm for directed acyclic graphs that breaks through the O(n²) barrier on the single-operation complexity of fully dynamic transitive closure, where n is the number of edges in the graph. We can answer queries in O(n^ε) worst-case time and perform updates in O(n^{ω(1,ε,1)−ε}+n^1+ε) worst-case time, for any ε∈[0,1], where ω(1,ε,1) is the exponent of the multiplication of an n × n^ε matrix by an n^ε × n matrix. The current best bounds on ω(1,ε,1) imply an O(n^0.575) query time and an O(n^1.575) update time in the worst case. Our subquadratic algorithm is randomized, and has one-sided error. As an application of this result, we show how to solve single-source reachability in O(n^1.575) time per update and constant time per query.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 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: Demetrescu, C., and Italiano, G. F. 2001. Maintaining dynamic matrices for fully dynamic transitive closure. Tech. Rep. arXiv:cs.DS/0104002.
• 4: 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
• 5: Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM (JACM), v.48 n.4, p.723-760, July 2001 [doi>10.1145/502090.502095]
• 6: Xiaohan Huang , Victor Y. Pan, Fast rectangular matrix multiplication and applications, Journal of Complexity, v.14 n.2, p.257-299, June 1, 1998 [doi>10.1006/jcom.1998.0476 ]
• 7: Ibaraki, T., and Katoh, N. 1983. On-line computation of transitive closure for graphs. Inf. Proc. Lett. 16, 95--97.
• 8: G. F. Italiano, Amortized efficiency of a path retrieval data structure, Theoretical Computer Science, v.48 n.2-3, p.273-281, Dec., 1986
• 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: Khanna, S., Motwani, R., and Wilson, R. H. 1998. On certificates and lookahead in dynamic graph problems. Algorithmica 21, 4, 377--394.
• 11: 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
• 12: Valerie King , Garry Sagert, A fully dynamic algorithm for maintaining the transitive closure, Journal of Computer and System Sciences, v.65 n.1, p.150-167, August 2002 [doi>10.1006/jcss.2002.1883]
• 13: 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
• 14: Munro, I. 1971. Efficient determination of the transitive closure of a directed graph. Inf. Proc. Lett. 1, 2, 56--58.
• 15: Piotr Sankowski, Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.509-517, October 17-19, 2004 [doi>10.1109/FOCS.2004.25]
• 16: Yellin, D. M. 1993. Speeding up dynamic transitive closure for bounded degree graphs. Acta Inf. 30, 369--384.
• 17: All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002 [doi>10.1145/567112.567114]

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
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

General Terms:
Algorithms

Keywords:
Dynamic graph algorithms, transitive closure