Transitive reduction of DAG

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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,
            Add V to Visited, 
            Initialise Indirect as the empty set,
            For each edge V -> W in G,
                Invoke Visit(W),
                Add Closure(W) to Indirect.
            Set Closure(V) to Indirect.
            For each edge V -> W in G,
                Add W to Closure(V),
                If W is in the set Indirect,
                    Delete the edge V -> W from G.

This assumes that you have some efficient way of keeping track of sets of vertices (e.g., bit maps), but I think this assumption is made in other O(V+E) algorithms too.

A potentially useful side-effect is that it finds the transitive closure of each vertex of G.

Answer 4

I solved the same problem but it was not exactly the same.It asked for the minimum no of edges in the graph after reduction such that the vertices originally connected are still connected and no new connections are made. As it is clear, it doesn't say to find the reduced graph but how many redundant edges are present. This problem can be solved in O(V+E). The link to explanation is https://codeforces.com/blog/entry/56326. But I think to make the graph actually, it will have high complexity than O(N)