A new approach to incremental topological ordering

Let G = (V, E) be a directed acyclic graph (dag) with n = |V| and m = |E|. We say that a total ordering ≺ on vertices V is a topological ordering if for every edge (u,v) ∈ E, we have u ≺ v. In this paper, we consider the problem of maintaining a topological ordering subject to dynamic changes to the underlying graph. That is, we begin with an empty graph G = (V, ∅) consisting of n nodes. The adversary adds m edges to the graph G, one edge at a time. Throughout this process, we maintain an online topological ordering of the graph G. In this paper, we present a new algorithm that has a total cost of O(n² log n) for maintaining the topological ordering throughout all the edge additions. At the heart of our algorithm is a new approach for maintaining the ordering. Instead of attempting to place the nodes in an ordered list, we assign each node a label that is consistent with the ordering, and yet can be updated efficiently as edges are inserted. When the graph is dense, our algorithm is more efficient than existing algorithms. By way of contrast, the best known prior algorithms achieve only O(min(m^1.5,n^2.5)) cost.