Take the 2-minute tour ×
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.

I'm trying to solve a graph problem (it's not for homework, just to practice my skills). A DAG $G(V,E)$ is given, where $V$ is the set of vertices and $E$ the edges. The graph is represented as an adjacency list, so $A_v$ is a set containing all the connections of $v$. My task is to find which vertices are reachable from each vertex $v\in V$. The solution I use has a complexity of $O(V^3)$, with transitive closure, but i read that in a blog it can be faster, although it didn't reveal how. Could anyone tell me another way (with better complexity) to solve the transitive closure problem in a DAG?

share|improve this question
    
Have a look at: stackoverflow.com/questions/3517524/… –  AJed Dec 7 '12 at 16:56
    
and this: cs.hut.fi/~enu/thesis.html –  AJed Dec 7 '12 at 16:57
    
However, my suggestion is to keep the $O(|V|^3)$. but just try to do decrease the number of comparisons on average. That is, make guesses and add simple rules to your algorithm. You can use matrix multiplication - but if you are using it for small graphs - then it is just a mess and in fact in practice your method is better. –  AJed Dec 7 '12 at 17:02
    
@AJed In this particular problem, $O(V^3)$ will exceed the time limit. –  Rondogiannis Aristophanes Dec 7 '12 at 17:05
2  
@RondogiannisAristophanes When you say time limit, do you mean that this is a problem in some programming/algorithm challenges like topcoder etc? If so, and if you are sure that you have correctly implemented an $O(V^3)$ solution, you might want to look at the problem again. There may be some other hidden property which might simplify things, or there might be a better way to express the problem so that a transitive closure is not needed. Because transitive closure is as hard as matrix multiplication. Read student.cs.uwaterloo.ca/~cs466/Old_courses/F08/… –  Paresh Dec 7 '12 at 19:03

1 Answer 1

The fact that our graph is acyclic makes this problem much simpler.

Topological sort can give us an ordering of the vertices $v_1,v_2,\dots,v_n$ such that, if $i < j$, then there is no edge from $v_j$ back to $v_i$. We've listed the vertices such that all edges in go "forward" in our list.

(edited to fix analysis and give slightly faster algorithm)

Now we just go backwards through this list, starting at the last vertex $v_n$. $v_n$'s transitive closure is just itself. Also add $v_n$ to the transitive closure of every vertex with an edge to $v_n$.

For each other vertex $v_i$, going from the end backwards, first add $v_i$ to its own transitive closure, then add everything in the transitive closure of $v_i$ to the transitive closure of all the vertices with an edge to $v_i$.

The running time is $O(n+m+nm) = O(n^3)$ in the worst case, with $n$ the number of vertices and $m \in O(n^2)$ the number of edges. Topological sort takes time $O(n+m)$. Then we do another $O(mn)$ work in the backward pass: As we go backwards through the list, for each edge, we have to add up to $n$ vertices to somebody's transitive closure.

Note that you can get a nice constant-factor speedup by representing everyone's transitive closure by bit-arrays. Say you only had $n=64$; then you would use a single 64-bit int where bit $i$ is 1 if $i$ is in my transitive closure and 0 otherwise. Then the part where we add everything in $i$'s transitive closure to $j$'s is really fast: We just take $c_j$ |= $c_i$. (Binary OR operation.)

For $n > 64$, you'd have to keep them in arrays and do some arithmetic, but it would be much faster than an Object set.

Also, I know the big-$O$ in the very worst case is still $O(n^3)$, but to beat this in practice you'd have to have something much more complex. This algorithm also does very well on sparse graphs.

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.