  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 $\tilde{O}(m^{4/3})$ total
expected update time.

Data Structures and Algorithms