Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

Abstract

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m^3/2) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n^5/2) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Ω(n²2^{√2 lg} n) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Θ(n² log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

References

1. Aho, A. V., Hopcroft, J. E., and Ullman, J. D. 1983. Data Structures and Algorithms. Addison-Wesley.
2. Ajwani, D. 2008. Traversing large graphs in realistic settings. Ph.D. thesis, Universität des Saarlandes, Saarbrücken, Germany.
3. Ajwani, D., Friedrich, T., and Meyer, U. 2006. An O(n ^2.75) algorithm for online topological ordering. In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT). 53--64.
4. Alpern, B., Hoover, R., Rosen, B. K., Sweeney, P. F., and Zadeck, F. K. 1990. Incremental evaluation of computational circuits. In Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA). 32--42.
5. Belik, F. 1990. An efficient deadlock avoidance technique. IEEE Trans. Comput. 39, 7, 882--888.
6. Bender, M. A., Cole, R., Demaine, E. D., Farach-Colton, M., and Zito, J. 2002. Two simplified algorithms for maintaining order in a list. In Proceedings of the 10th European Symposium on Algorithms (ESA). 152--164.
7. Bender, M. A., Fineman, J. T., and Gilbert, S. 2009. A new approach to incremental topological ordering. In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1108--1115.
8. Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., and Tarjan, R. E. 1973. Time bounds for selection. J. Comput. Syst. Sci. 7, 4, 448--461.
9. Cheriyan, J. and Mehlhorn, K. 1996. Algorithms for dense graphs and networks on the random access computer. Algorithmica 15, 6, 521--549.
10. Dey, T. K. 1998. Improved bounds for planar k-sets and related problems. Disc. Comput. Geom. 19, 3, 373--382.
11. Dietz, P. F. and Sleator, D. D. 1987. Two algorithms for maintaining order in a list. In Proceedings of the 19th ACM Symposium on Theory of Computing (STOC). 365--372.
12. Dor, D. and Zwick, U. 1999. Selecting the median. SIAM J. Comput. 28, 5, 1722--1758.
13. Gabow, H. N. 2000. Path-based depth-first search for strong and biconnected components. Inf. Proc. Lett. 74, 3--4, 107--114.
14. Haeupler, B., Kavitha, T., Mathew, R., Sen, S., and Tarjan, R. E. 2008a. Faster algorithms for incremental topological ordering. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP). 421--433.
15. Haeupler, B., Sen, S., and Tarjan, R. E. 2008b. Incremental topological ordering and strong component maintenance. http://arxiv.org/abs/0803.0792.
16. Han, Y. and Thorup, M. 2002. Integer sorting in O(n√log log n) expected time and linear space. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS). 135--144.
17. Harary, F., Norman, R. Z., and Cartwright, D. 1965. Structural Models : An Introduction to the Theory of Directed Graphs. Wiley.
18. Hoare, C. A. R. 1961. Algorithm 65: Find. Comm. ACM 4, 7, 321--322.
19. Katriel, I. 2004. On algorithms for online topological ordering and sorting. Tech. rep. MPI-I-2004-1-003, Max-Planck-Institut für Informatik, Saarbrücken, Germany.
20. Katriel, I. and Bodlaender, H. L. 2006. Online topological ordering. ACM Trans. Algor. 2, 3, 364--379.
21. Kavitha, T. and Mathew, R. 2007. Faster algorithms for online topological ordering. http://arxiv.org/abs/0711.0251.
22. Knuth, D. E. 1972. Mathematical analysis of algorithms. In Proceedings of the IFIP Congress. 19--27.
23. Knuth, D. E. 1973. The Art of Computer Programming. Vol. 1: Fundamental Algorithms. Addison-Wesley.
24. Knuth, D. E. and Szwarcfiter, J. L. 1974. A structured program to generate all topological sorting arrangements. Inf. Proc. Lett. 2, 6, 153--157.
25. Liu, H.-F. and Chao, K.-M. 2007. A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering. Theor. Comput. Sci. 389, 1--2, 182--189.
26. Liu, H.-F. and Chao, K.-M. 2008. An Õ(n ^2.5)-time algorithm for online topological ordering. http://arxiv.org/abs/0804.3860.
27. Marchetti-Spaccamela, A., Nanni, U., and Rohnert, H. 1993. On-line graph algorithms for incremental compilation. In Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 70--86.
28. Marchetti-Spaccamela, A., Nanni, U., and Rohnert, H. 1996. Maintaining a topological order under edge insertions. Inf. Proc. Lett. 59, 1, 53--58.
29. Nivasch, G. 2008. An improved, simple construction of many halving edges. In Surveys on Discrete and Computational Geometry: Twenty Years Later. AMS, 299--305.
30. Omohundro, S. M., Lim, C.-C., and Bilmes, J. 1992. The Sather language compiler/debugger implementation. Tech. rep. TR-92-017, International Computer Science Institute, Berkeley.
31. Pearce, D. J. 2005. Some directed graph algorithms and their application to pointer analysis. Ph.D. thesis, University of London, London, UK.
32. Pearce, D. J. and Kelly, P. H. J. 2003. Online algorithms for topological order and strongly connected components. http://homepages.ecs.vuw.ac.nz/~djp/files/tr0903.pdf.
33. Pearce, D. J. and Kelly, P. H. J. 2006. A dynamic topological sort algorithm for directed acyclic graphs. J. Exp. Algorithmics 11, 1.7.
34. Pearce, D. J. and Kelly, P. H. J. 2007. A dynamic batch algorithm for maintaining a topological order. Tech. rep., Victoria University, Wellington, New Zealand.
35. Pearce, D. J., Kelly, P. H. J., and Hankin, C. 2003. Online cycle detection and difference propagation for pointer analysis. In Proceedings of the IEEE Workshop on Source Code Analysis and Manipulation (SCAM). 3--12.
36. Ramalingam, G. and Reps, T. W. 1991. On the computational complexity of incremental algorithms. Tech. rep. CS-TR-1991-1033, University of Wisconsin-Madison.
37. Ramalingam, G. and Reps, T. W. 1994. On competitive on-line algorithms for the dynamic priority-ordering problem. Inf. Proc. Lett. 51, 3, 155--161.
38. Roditty, L. and Zwick, U. 2008. Improved dynamic reachability algorithms for directed graphs. SIAM J. Comput. 37, 5, 1455--1471.
39. Schönhage, A., Paterson, M., and Pippenger, N. 1976. Finding the median. J. Comput. Syst. Sci. 13, 2, 184--199.
40. Sharir, M. 1981. A strong-connectivity algorithm and its applications in data flow analysis. Comput. Math. App. 7, 1, 67--72.
41. Sharir, M. and Smorodinsky, S. 2003. Extremal configurations and levels in pseudoline arrangements. In Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS). 127--139.
42. Shmueli, O. 1983. Dynamic cycle detection. Inf. Proc. Lett. 17, 4, 185--188.
43. Szpilrajn, E. 1930. Sur l’extension de l’ordre partiel. Fund. Math. 16, 386--389.
44. Tamaki, H. and Tokuyama, T. 2003. A characterization of planar graphs by pseudo-line arrangements. Algorithmica 35, 3, 269--285.
45. Tarjan, R. E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 2, 146--160.
46. Tarjan, R. E. 1975. Efficiency of a good but not linear set union algorithm. J. ACM 22, 2, 215--225.
47. Tarjan, R. E. and van Leeuwen, J. 1984. Worst-case analysis of set union algorithms. J. ACM 31, 2, 245--281.
48. Thorup, M. 2004. Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci. 69, 3, 330--353.
49. Tóth, G. 2001. Point sets with many k-sets. Discrete Comput. Geom. 26, 2, 187--194.
50. van Emde Boas, P. 1977. Preserving order in a forest in less than logarithmic time and linear space. Inf. Proc. Lett. 6, 3, 80--82.
51. van Emde Boas, P., Kaas, R., and Zijlstra, E. 1977. Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99--127.
52. Zwick, U. 1986. Allowable circular sequences and their application (in Hebrew). M.S. thesis, Tel-Aviv University, Tel-Aviv, Israel.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Theory of computation

  • Randomness, geometry and discrete structures