CODEWITHSUNDEEP
algorithmgraphgraph-theory
JohnA
JohnA

Reputation: 341

Efficient algorithm for finding all edges that induce a cycle

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?

Upvotes: 1

Views: 634

Answers (2)

bigballer
bigballer

Reputation: 146

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.

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65508

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.

Upvotes: 1

Related Questions