find an algorithm that calculates the transitive closure of a directed graph using O(n 4 ) time

Question

for an assignment I am asked by to find find an algorithm that calculates the transitive closure of a directed graph using O(n 4 ) time. We already learned about the floyd warshall algorithm, which is a lot better, so can someone help me create one that runs in O(n4) time? is there such an algorithm?

I know it seems dumb of a question. I dont really understand why we are being asked to find the slower way to do it.

Answer 1

Floyd Warshall is O(n^3), and since O(n^3) is a subset of O(n^4), it is also O(n^4).
Thus, by setting a new graph G'=(V,E',w') where E' = V x V (clique, complete graph) and w'(u,v) = 1 if (u,v) is in E, otherwise INFINITY - by using Floyd-Warshall algorithm, each pair (u,v) that ends up with a value less then infinity is in the closure.

---

A Theta(n^4) solution:

Q <- E (init) #(Q is a set)
for i from 1 to n:
   for each v in V:
     for each w in V:
        for each u in V:
            if (v,w) is in Q and (w,u) is in E:
               Q <- Q U {(v,u)}  #add (v,u) to Q

Complexity is trivially Theta(n^4), we only need to show it indeed finds the transitive closure.

By induction:

1. For shortest path of length 1 from u to v it is the base clause, since (u,v) is in E.
2. For each k:
   Each pair (u,v) with shortest path of length k>1 - there is w such that there is a path u -> ... -> w, and an edge (w,v). From induction hypothesis, in previous iterations we added (u,w) to Q, and thus the condition will yield true, and we will add (u,v) to the resulting set Q.

Similary show that if some pair (u,v) was added to Q, then there is a path u->..->w->v, and thus it was rightfully added.

---

A second Theta(n^4) solution:

Set G' as described above, and for each vertex v in V run Bellman Ford from v.
Each run of BF is Theta(n^3)¹, running it n times is Theta(n^4)

---

(1) Technically it is O(VE), but for none sparse graphs E is in Theta(V^2)

Answer 2

The Floyd-Warshall Algorithm for transitive closure looks like:

int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
// If the nodes are unconnected, dist[i][j] should be infinity

for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
   if(dist[i][k] && dist[k][j])
      dist[i][j] = 1;

Note the order of the indices used: they are ordered this way to preserve an optimal substructure property. If we instead reorder them as below, that property is violated:

  for ( i = 0; i < N; i++ ) 
  for ( j = 0; j < N; j++ )
  for ( k = 0; k < N; k++ )
    if(dist[i][j] && dist[j][k])
      dist[i][k]=1;

The result of violating the property is that the transitive closure paths grow (at worst) only one link in the O(n^3) iterations above. In order to ensure that they transitive closure paths grow all the way, we need to keep iterating until they stop growing:

do{
  something_done=false;
  for ( i = 0; i < N; i++ ) 
  for ( j = 0; j < N; j++ )
  for ( k = 0; k < N; k++ )
    if(dist[i][j] && dist[j][k]){
      dist[i][k]=1;
      something_done=true;
    }
} while (something_done);

If the outer loop is in O(N), then the algorithm itself is in O(N^4).

Unfortunately, it may not be possible to (easily) show that the outer loop has that property, since it is particular to the data.