Transitive reduction of DAG

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.

• You cannot use the reference given in the wikipedia lemma you cite? Dec 2 '12 at 10:32
• Well, the algorithm discussed in the Wikipedia runs in $O(V\times E)$ (in the best case, i.e., in the case of acyclic graphs) instead of $O(V+E)$ as requested. I think the right answer here is that the algorithm you are currently looking for might not exist Dec 2 '12 at 11:12
• Agreed that it is not clear that what you're asking for exists. There are quite a few papers that would be uninteresting if there was such an algorithm, for example, sciencedirect.com/science/article/pii/0012365X9390164O. That said, if you can be more specific about what your motivation is, there may be more specific solutions. For example, do you know anything else about the graph or would $O(n(n+m))$ work? Dec 2 '12 at 22:22
• I saw the problem somewhere, but there was no additional information, maybe a typo in the problem. Dec 6 '12 at 18:37
• What if you do topological sort in your DAG, but keep track of reachable vertices by using children, i.e $reachable[v] = \cup_{v' \in children_v} reachable[v']$, then start from latest item in sorted graph, and remove unused edges and go up by preserving reachable function, this gives you maximal possible edges to remove, but I'm not sure if it gets maximum possibility (it's $O(|E|+|V|)$.
– user742
Dec 7 '12 at 9:57

We can solve this problem just by doing DFS from each vertex.

1. 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.
2. 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))$.

• Note that, asymptotically, this has the same complexity as the $O(NM)$ algorithm in the Wikipedia article linked in the question itself. Aug 14 '14 at 20:06
• Agreed. Since a concise answer was due for this question, I've presented one. Further, an $O(N)$ solution is IMO, unlikely. Aug 14 '14 at 20:38

Not what you are looking for. But just for the purpose sharing knowledge, you can do that with $$O(|E|)$$ messages if you assume that each vertex to act as a processor. Note each vertex has a comparable value. Therefore, there exists some vertices such that they are larger than all their neighbors. These vertices do the following:

1. Let $$u$$ be the maximum smaller neighbor of $$v$$,
2. send a message to $$u$$ and include edge $$(v,u)$$ in the output.
3. For every neighbor $$w$$ of $$u$$ and $$v$$ (and smaller than both), do not include $$(v,w)$$ in the output.
4. Repeat the steps until all edge $$(v,v')$$ for a smaller neighbor $$v'$$ of vertex $$v$$ is either included or not included in the output.

Now if a node $$v$$ received a message from every larger neighbor (i.e. all the edges $$(v',v)$$ are either included or not included, then node $$v$$ acts as if it was the largest in its neighborhood. That is, it performs the previously mentioned 4 steps.

This algorithm terminates in $$O(|E|)$$ messages in a distributed environment. I know this is not what you are asking for.

Lemma: If there is an edge V -> Y and Y is also an indirect successor of V, (e.g., V -> W ->+ Y) then the edge V -> Y is transitive and not part of the transitive root.

Method: Keep track of the transitive closure of each vertex, working from terminal to initial vertices in reverse topological order. The set of indirect successors of V is the union of the transitive closures of the immediate successors of V. The transitive closure of V is the union of its indirect successors and its immediate successors.

Algorithm:

Initialise Visited as the empty set.
For each vertex V of G,
Invoke Visit(V).

Visit(V):
If V is not in Visited,
Initialise Indirect as the empty set,
For each edge V -> W in G,
Invoke Visit(W),