patternModerate
Transitive reduction of DAG
Viewed 0 times
dagreductiontransitive
Problem
I am looking for O(V+E) algorithm for finding the transitive reduction given a DAG.
That is remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still reach after removal of edges.
If this is a standard problem, please point me to some model solution.
That is remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still reach after removal of edges.
If this is a standard problem, please point me to some model solution.
Solution
We can solve this problem just by doing DFS from each vertex.
The overall complexity of the above is the complexity of running $N$ DFS', which is $O(N(N+M))$.
- For each vertex $u \in G$, start the DFS from each vertex $v$ such that $v$ is the direct descendant of $u$, ie. $(u,v)$ is an edge.
- For each vertex $v'$ reachable by the DFS from $v$, remove the edge $(u, v')$.
The overall complexity of the above is the complexity of running $N$ DFS', which is $O(N(N+M))$.
Context
StackExchange Computer Science Q#7096, answer score: 12
Revisions (0)
No revisions yet.