Efficient algorithm for finding all edges that induce a cycle

Question

What is the fastest way to find all edges that would induce a cycle in a directed acyclic graph, if added to the graph?

Formally: Suppose you have a DAG $G=(V,E)$ with edge set $E\subset V\times V$. Find all $e\in V\times V-E$ such that the graph $G(e)=(V,E\cup{e})$ has at least one cycle.

The brute-force approach would be to use DFS to check if $G(e)$ has a cycle for all $e\in V\times V-E$. Is there a faster method?

Answer 1

Observation: an edge induces a cycle if and only if [it's a self loop or its reverse edge belongs to the transitive closure of the DAG]. The problem of computing the transitive closure is thus essentially equivalent to this one. Sadly, the fastest known algorithms in theory are based on fast matrix multiplication and are thus hopelessly impractical.

If you're interested in computing the transitive closure of a large DAG in practice, Wikipedia links to Esko Nuutila's thesis on the subject.

Answer 2

For each node X, DFS or BFS its parents & parents parents etc. Each of these edges (from X to any of its parents) would create a cycle. Performance is O(c) + O(|V|) where c is the number of edges that would induce a cycle.

I also suggest you try implement topological sorting, it will be good practice for you and is a similar concept.