Check if adding an edge to a DAG results in a cycle

Question

On the begining: It is a programming contest problem, but not from on-going one. Unfortunatelly, I can't provide any link to this task, because it is not publically available. It was from one of the Polish local programming contest in 2011 organised by Warsaw School of Computer Science.

I have a graph with $V$ $(1 \le V \le 5 \cdot 10^5)$ vertices without edges and a list of $E$ $(1 \le E \le 5 \cdot 10^5)$ directed edges. On the $i$-th second $i$-th edge is being added to a graph. I want to know after which second there will be a cycle in a graph.

The most obvious solution would be to perform DFS after adding each edge, but it would take $O((V + E)^2)$ time. Another solution would be to keep the graph topologically sorted and when adding an edge, I could place it in such a way so that it will not disturb topological ordering. This would take at most $O(V^2)$ time. I did some research on Google and it seems that this is the fastest online algorithm.

As I know all the edges beforehand I can use offline algorithm. The fastest offline algorithm I can think of is binary search. If after $k$-th second graph contains a cycle then obviously it will have a cycle at any other second $l \ge k$. So I can do binary search to find smallest $k$ by performing DFS $O(\log E)$ times, each of them taking $O(V + E)$ time, so the total complexity of this solution would be $O((V + E) \log E)$.

It is quite fast, but I wonder if there exist any faster offline algorithm. One thing I can think of is giving for each edge weight equal to the time when this edge was added to a graph. Then the task would be equivalent to finding a cycle with minimal maximum edge weight. I don't know if it leads to anywhere.

Answer 1

KWillets' algorithm

KWillets seems to have the best algorithm. Basically, you iteratively alternate between the following two steps:

1. For each source (vertex with no outgoing edge), remove the source and all edges leading out from it. Repeat until there are no more sources.

2. Remove the highest-numbered edge, i.e., the one that is at the latest time (out of all remaining edges). Go back to step 1.

When the graph is empty, undo the last step 1 and step 2, and there's the earliest graph with a cycle. In other words, take the last edge removed in the last step 2 before the graph becomes empty, and the graph containing that edge and all earlier edges is the first one containing a cycle.

Since your list of edges is already sorted by increasing time, this can be implemented in $O(V+E)$ time. You'll maintain the list of edges in a doubly-linked list, with pointers between those nodes and the corresponding edge in the graph. Step 1 requires $O(1)$ time per node or edge deleted, if you keep a separate worklist of all source vertices and any time you delete an edge you check whether that has created a new source vertex.

Binary search

It's possible to make some small optimizations to your binary search method, though they won't improve the asymptotic running time: the asymptotic running time will still be $O((V+E)\log E)$.

Suppose you analyze the graph at time $k$, and discover that it does contain a cycle. Decompose the graph into strongly connected components. Now you can permanently delete all isolated nodes (i.e., nodes that are in a SCC of size 1); they cannot be part of a cycle. You can continue the binary search from here.

Also, when you decompose into strongly connected components, for each strongly connected component, do the following. Count the number of nodes in the SCC, say $n_0$ of them. Sort the edges within the SCC in increasing time. Look at the time of the $n_0$th of them, say time $j_0$. Then the first time when there is a cycle within that strongly connected component must be time $j_0$ or later. Do this for each strongly connected component, and take the earliest of those times. Then, as an optimization, there is no need to consider any time earlier than that during the binary search.

However, these two optimizations probably won't provide more than a small constant-factor speedup, at best.

Answer 2

Kahn's algorithm is known for topological sorting, but it can be used to find strongly connected components as well. I use it for cycle checking, where an actual topological sort is not needed. In this variant, nodes are discarded as they are visited, instead of being added to the output, and the error termination indicates at least one cycle.

It works by pruning off root or leaf nodes (having in-degree or out-degree 0 resp.) from the graph one at a time, until no more nodes of that type can be found. Since this process cannot cut a cycle (all nodes on a cycle have indegree and outdegree > 0), it terminates with a nonempty graph if at least one cycle exists.

If we cut the maximum remaining edge e at each such termination point, we can continue the process to see if E\e still contains a cycle, and so on iteratively until we've cut enough edges to make E acyclic. The last such edge cut k is the first k that makes E[1...k] cyclic.

Kahn's algorithm does this leaf-cutting process linearly by using a work queue of nodes to be deleted; it is initialized with the leaves of the entire graph (at least one of which must exist, if it's acyclic), and, as each is deleted, its parent node(s) are checked to see they in turn become leaves, and if so they are added to the work queue. By checking the neighborhood of each deletion, it works linearly through the graph, without the need for indexing structures beyond the FIFO queue.

We can do the same neighbor-leafness check as we cut the maximum edge, and add any leaves created to the work queue, or, if none are created, continue cutting.

In order to make the max-cutting process linear, we have to find the maximum non-deleted edge via a descending scan of the edges array, but each scan starts where the previous left off, and the algorithm only does a single pass through the whole array, so that part is O(E) in total. Overall I believe this method is O(V+E), the same as Kahn's alone.