1
$\begingroup$

Suppose that we are given a directed graph and we want to find out if a vertex $j$ is reachable from another vertex $i$ for all vertex pairs $(i, j)$ in the given graph. Reachable mean that there is a path from vertex $i$ to $j$. The reachability matrix is called transitive closure of a graph.

I want to write an algorithm that rus in time $O(|V| \cdot |E|)$ and calculates the transitive closure of a directed graph $G=(V,E)$.

I have tried the following:

 Transitive_Closure(G) 
         for v=1 to |V| 
               for u=1 to |V| 
                        T(v,u)=0
         for v=1 to |V| 
                for each u in Adj[v] 
                        T(v,u)=1 
                        for each w in Adj[u] 
                                T(v,w)=1

But isn't the time complexity $O(|V| \cdot |E|^2)$? Or am I wrong?

This algorithm definitely finds the transition matrix, but it's even in $\Omega(|V|^3)$:

    Transitive_Closure(G)
      for i = 1 to |V| 
          for j = 1 to |V| 
              T[i,j]=A[i,j] // A is the adjacency matrix of G
      for k = 1 to |V|
          for i = 1 to |V|
              for j = 1 to |V|
                  T[i,j]=T[i,j] OR (T[i,k] AND T[k,j])

EDIT: Is the following algorithm right?

Transitive_Closure(G)
1.  for each vertex u in G.V
2.       for each vertex v in G.V
3.            T[u,v]=0
4.   for each vertex u in G.V
5.        BFS(G,u)
6.   return T 



BFS(G,s)
1.  for each vertex u in G.V-{s}
2.       color[u]=WHITE
3.       d[u]=inf
4.       pi[u]=NIL
5.  color[s]=GRAY
6.  d[s]=0
7.  pi[s]=NIL
8.  Q=empty set
7.  ENQUEUE(Q,s)
8.  while Q!= empty set
9.          u=DEQUEUE(Q)
10.        for each v in G.Adj[u]
11.             if color[v]==WHITE
12.                color[v]=GRAY
13.                d[v]=d[u]+1
14.                pi[v]=u
17.                ENQUEUE(Q,v)
18.        color[u]=BLACK
19.        T[s,u]=1
$\endgroup$
  • $\begingroup$ Your algorithm is actually better than that bound you give. Hint: how often do you investigate each edge? $\endgroup$ – Raphael Apr 14 '15 at 16:53
  • $\begingroup$ @Raphael Do you mean the second algorithm? The first two for-loops are executed together $O(|V|^2)$ times. After that isn't each for-loop executed $O(|V|)$ times? $\endgroup$ – Mary Star Apr 14 '15 at 16:56
  • $\begingroup$ I meant the first. $\endgroup$ – Raphael Apr 14 '15 at 16:57
  • $\begingroup$ @Raphael Yes, Yuval noticed that the time complexity should be $O(V \cdot E)$. But it doesn't give a right result. Could you give me a hint what I could do, in order to write an algorithm that finds the reachability matrix in time $O(V \cdot E)$ ? $\endgroup$ – Mary Star Apr 14 '15 at 16:59
  • $\begingroup$ pastebin.com/sikzBuiG I changed something.. But we still don't have the desired time complexity. So do we have to avoid the two nested for-loops at the beginning? @YuvalFilmus $\endgroup$ – Mary Star Apr 14 '15 at 17:40
2
$\begingroup$

This algorithm doesn't work. Consider a graph with four vertices 1,2,3,4 and edges $1\to2\to3\to4$. Your algorithm outputs $T(1,4)=0$ even though 4 is reachable from 1.

The running time analysis of the algorithm can be improved to $O(VE)$. The first loop takes time $O(V^2)$. The number of pairs $(v,u)$ in the second loop is the number of edges $E$, and for each pair $(v,u)$, the maximal number of $w$s is $V$. So the second loop runs in time $O(VE)$.

$\endgroup$
  • $\begingroup$ I see, Yuval Filmus. I added at my initial post an algorithm that finds the reachability matrix, but its time complexity is $O(V^3)$. Could I change something? Or is the general idea wrong? $\endgroup$ – Mary Star Apr 14 '15 at 16:50
2
$\begingroup$

This answer summarizes some of the comments. The well-known Floyd–Warshall algorithm runs in time $O(V^3)$, and there is a matrix multiplication based algorithm running in time $O(V^\omega)$, which is however not so useful in practice.

The following algorithm runs in time $O(V(V+E))$. Starting at each vertex $v$, run a DFS/BFS from $v$ to find all nodes reachable from $v$. This is not quite $O(VE)$, but given that the output size $V^2$, the $V^2$ term in the running time is unavoidable.

What if we don't want to output the entire matrix, but only the non-zero entries? In this case we can modify this algorithm to run in time $O(VE)$. First we use DFS/BFS to find all the connected components. Let $V_i,E_i$ be the number of vertices and edges in the $i$th component, and note that $E_i \geq V_i-1$. We run the previous algorithm on each connected component, thus achieving a running time of $O(\sum_i V_i(V_i+E_i)) = O(\sum_i V_iE_i)$. Using $V_i \leq V$ and $\sum_i E_i = E$, we see that the overall running time is $O(VE)$ (in addition to $O(V+E)$ for the initial BFS/DFS).

In fact, this modification isn't really needed. The running time of BFS/DFS in component $i$ is $O(V_i+E_i) = O(E_i)$, and so the running time of the original algorithm is in fact only $O(\sum_i V_i E_i) = O(VE)$, given that we don't output the entire matrix but only the non-zero entries.

$\endgroup$
  • $\begingroup$ I edited my post and added an algorithm. Could you tell me if it is right? $\endgroup$ – Mary Star Apr 16 '15 at 16:54
  • 1
    $\begingroup$ @evinda I'm not going to check your algorithm. Try to compare it against some other algorithm you trust on some graphs, and see if you get the same results. Also, try to prove that your algorithm works. $\endgroup$ – Yuval Filmus Apr 16 '15 at 17:18
  • $\begingroup$ Even if we output only the non-zero entries, don't we have to initialize the array at the beginning, which requires $O(|V|^2)$ time? $\endgroup$ – Mary Star Apr 24 '15 at 16:58
  • $\begingroup$ Not necessarily. It depends on the implementation. You don't have to keep the entire matrix. $\endgroup$ – Yuval Filmus Apr 24 '15 at 17:34
  • $\begingroup$ How can we implement the algorithm so that we don't have to initialize the matrix? $\endgroup$ – Mary Star Apr 24 '15 at 17:37

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.