Fast algorithm to remove edge to get DAG

Question

Given a directed cyclic graph, I want to find if removing a single edge can make the graph a DAG. I came up with a trivial way to do this - remove each edge and check if the graph is cyclic (which takes $\mathcal{O}(\mid E \mid(\mid V \mid + \mid E \mid))$ time, but I'm wondering if there's a faster way to do this.

Answer 1

Consider the rooted spanning tree formed by a DFS traversal. You need to study the back edges. Here's a picture from Wikipedia showing the different type of edges generated by the traversal:

If you only have one back edge, you can remove it and get a DAG. If you have multiple back edges, you need to find a common, shared tree edge to remove, and it should be one that can't be circumvented using a forward or cross edge.

1. Generate the DFS traversal tree ($\mathcal{O}(|E| + |V|)$).

2. We can find the LCA of all the lower (starting) vertices of our back edges ($\mathcal{O}(|E|\log|V|)$). Call this vertex $b$ (bottom).

3. We can find the lowest ending (top) vertex of a back edge in the DFS tree. Call this vertex $t$ (top). To do this step, it would be handy to remember vertex level when doing the traversal. $\mathcal{O}(|E|)$

4. If $t$ is lower in the tree than $b$, then we have two back edges that don't "share" a common tree edge that can be removed remove, so we would need to remove both of them to get a DAG. Otherwise, we need to interrupt the path along the tree from $t$ to $b$. We can try to do that by removing an edge on it.

5. We need to check if all the tree edges from $t$ to $b$ can be circumvented. That can happen via forward edges, or via a branch and then a cross edge. Thus, we can remove them all, and check if there's still a path from $t$ to $b$. If not, then there is a tree edge between them that is essential to all cycles ($\mathcal{O}(|E| + |V|)$).