13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You cannot use the reference given in the wikipedia lemma you cite? $\endgroup$ – Hendrik Jan Dec 2 '12 at 10:32
  • 2
    $\begingroup$ 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 $\endgroup$ – Carlos Linares López Dec 2 '12 at 11:12
  • 1
    $\begingroup$ 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? $\endgroup$ – William Macrae Dec 2 '12 at 22:22
  • $\begingroup$ I saw the problem somewhere, but there was no additional information, maybe a typo in the problem. $\endgroup$ – Karan Dec 6 '12 at 18:37
  • 1
    $\begingroup$ 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|)$. $\endgroup$ – user742 Dec 7 '12 at 9:57
8
$\begingroup$

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

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've deleted the answer posted on your earlier account. If you still wish to merge your two accounts, please follow the steps in the help center. That being said, since the earlier account no longer has any visible content, you could just stick to the new one. $\endgroup$ – Gilles Nov 11 '17 at 12:03
0
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.