Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 3 down vote favorite

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.

share|improve this question
You cannot use the reference given in the wikipedia lemma you cite? – Hendrik Jan Dec 2 '12 at 10:32
1  
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 – Carlos Linares López 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? – William Macrae Dec 2 '12 at 22:22
I saw the problem somewhere, but there was no additional information, maybe a typo in the problem. – Karan 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|)$. – Saeed Amiri Dec 7 '12 at 9:57

1 Answer

up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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