[Solved]: Check if adding an edge to a DAG results in a cycle

Problem Detail: 

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.

Asked By : J. Abraham

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65633

3.2K people like this

 Download Related Notes/Documents