Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan · ACM Transactions on Algorithms · 2012
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 √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 2 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.