# Efficient algorithm for retrieving the transitive closure of a directed acyclic graph

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?

• Have a look at: stackoverflow.com/questions/3517524/…
– AJed
Dec 7, 2012 at 16:56
• and this: cs.hut.fi/~enu/thesis.html
– AJed
Dec 7, 2012 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, 2012 at 17:02
• @AJed In this particular problem, $O(V^3)$ will exceed the time limit. Dec 7, 2012 at 17:05
• @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/… Dec 7, 2012 at 19:03

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.

• You could likely use a linked list representation for the sets and they would end up sharing common tails. Sep 10, 2018 at 21:19
• You can compute SCCs in linear (O(E+V)) time and then do the closure over the acyclic graph of SCCs (Purdom's algorithm), so having the graph be acyclic already doesn't actually affect the worst case complexity. Jul 31, 2021 at 5:52

Purdom's algorithm computes the transitive closure of a DAG in $$\mathcal{O}\left(\vert E \vert + \mu \vert V\vert \right)$$ , where $$\mu \le \vert V \vert$$ is the number of strongly connected components of the graph. Since $$\vert E\vert = \mathcal{O}\left(\vert V \vert^2\right)$$, Purdom's runtime is $$\mathcal{O}\left(\vert V \vert^2\right)$$, i.e. faster than your stated $$\mathcal{O}\left(\vert V \vert^3\right)$$ algorithm.

• I think the complexity analysis on the page you linked is wrong. In step 3, you iterate over the edges in the reduced acyclic graph, and thus step 3 has complexity O(EV) where E and V are the number of edges and vertices in the reduced graph. Since in the worst case, every node is an SCC, this leads to O(EV) overall complexity. Jul 31, 2021 at 5:50
• Are you sure you need to iterate through all edges? Dec 4 at 15:04