Incremental SCC maintenance in sparse graphs

In the incremental cycle detection problem, edges are added to a directed graph (initially empty), and the algorithm has to report the presence of the first cycle, once it is formed. A closely related problem is the incremental topological sort problem, where edges are added to an acyclic graph, and the algorithm is required to maintain a valid topological ordering. Since these problems arise naturally in many applications such as scheduling tasks, pointer analysis, and circuit evaluation, they have been studied extensively in the last three decades. Motivated by the fact that in many of these applications, the presence of a cycle is not fatal, we study a generalization of these problems, incremental maintenance of strongly connected components (incremental SCC). Several incremental algorithms in the literature which do cycle detection and topological sort in directed acyclic graphs, such as those by [7] and [16], also generalize to maintain strongly connected components and their topological sort in general directed graphs. The algorithms of [16] and [7] have a total update time of O(m³/²) and O(m · min{m¹/², n²/³}) respectively, and this is the state of the art for incremental SCC. But the most recent algorithms for incremental cycle detection and topological sort ([8] and [10]), which yield total (randomized) update time Õ(min{m⁴/³, n²}), do not extend to incremental SCC. Thus, there is a gap between the best known algorithms for these two closely related problems. In this paper, we bridge this gap by extending the framework of [10] to general directed graphs. More concretely, we give a Las Vegas algorithm for incremental SCCs with an expected total update time of Õ(m⁴/³). A key ingredient in the algorithm of [10] is a structural theorem (first introduced in [8]) that bounds the number of “equivalent” vertices. Unfortunately, this theorem only applies to DAGs. We show a natural way to extend this structural theorem to general directed graphs, and along the way we develop a significantly simpler and more intuitive proof of this theorem.