An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs

We consider the problem of incremental cycle detection and topological ordering in a directed graph G = (V, E) with |V | = n nodes. In this setting, initially the edge-set E of the graph is empty. Subsequently, at each time-step an edge gets inserted into G. After every edge-insertion, we have to report if the current graph contains a cycle, and as long as the graph remains acyclic, we have to maintain a topological ordering of the node-set V . Let m be the total number of edges that get inserted into G. We present a randomized algorithm for this problem with Õ(m 4/3 ) total expected update time.

Our result improves the Õ(m • min(m 1/2 , n 2/3 )) total update time bound of [BFGT16; HKMST08; HKMST12; CFKR13]. Furthermore, whenever m = o(n 3/2 ), our result improves upon the recently obtained Õ(m √ n) total update time bound of [BC18]. We note that if m = Ω(n 3/2 ), then the algorithm of [BFGT16; BFG09; CFKR13], which has Õ(n 2 ) total update time, beats the performance of the Õ(m √ n) time algorithm of [BC18]. It follows that we improve upon the total update time of the algorithm of [BC18] in the "interesting" range of sparsity where m = o(n 3/2 ).

Our result also happens to be the first one that breaks the Ω(n √ m) lower bound of [HKMST08] on the total update time of any local algorithm for a nontrivial range of sparsity. Specifically, the total update time of our algorithm is o(n √ m) whenever m = o(n 6/5 ). From a technical perspective, we obtain our result by combining the algorithm of [BC18] with the balanced search framework of [HKMST12].