1
$\begingroup$

Consider the following inefficient algorithm that decides if there is a path between two vertices s and t of a directed graph G. Show that the algorithm is correct. In addition, analyze its complexity and compare it with the other path between two vertices algorithms (Dijsktra, Bellman-Ford Algorithm, etc.) and explain why this algorithm is inefficient.

ALGORITHM Reachable(G, s, t)
     RETURN A(G,s,t,|V(G)|)
END Reachable

FUNCTION A(G,s,t,d)
     IF d=1 THEN
        IF s == t OR there is a directed edge (s,t) in G THEN
              RETURN TRUE
        ELSE
              RETURN FALSE
     ELSE
          FOR each vertex v in G DO
              IF A(G,s,v,d/2) AND A(G,v,t,d/2) THEN
                   RETURN TRUE
              ENDIF
          ENDFOR
          return FALSE
END A

I tried to prove correctness using invariants, but I'm not sure if that's the best way to prove it. Could you help me, please?

And I tried to obtain time complexity considering the for-loop, but also I have doubts.

Thanks a lot for your help!

$\endgroup$
  • 1
    $\begingroup$ Exactly as presented, the pseudocode looks incorrect. Specifically, what is d/2? If it's real number division, it may never become 1. If it's integer division rounding down, I think it does not work with a graph which is just a path of 7 vertices and 6 edges. May work if d/2 is rounding up, but that must be specified since it is not implied by such notation. $\endgroup$ – Gassa Dec 30 '18 at 12:55
  • $\begingroup$ Another minor nitpick is that both = and == are used for checking equality. It's best to pick one and stick to it, as it would make reading, and perhaps translating to an actual programming language, less surprising. $\endgroup$ – Gassa Dec 30 '18 at 12:57
1
$\begingroup$

If we interpret d/2 as real number division, then A(G,s,t,3) will run forever. If we interpret d/2 as integer division such as 3/2=1, then the algorithm will fail for a graph which is just a path of 6 vertices and 5 edges. If we interpret d/2 rather unnaturally as integer division of d+1 by 2, the algorithm becomes correct but the semantic of A(G,s,t,d) is not very natural either.

Hence, we will change the following part of the algorithm

              IF A(G,s,v,d/2) AND A(G,v,t,d/2) THEN
                   RETURN TRUE
              ENDIF

to

              IF A(G,s,v,d/2) AND A(G,v,t,(d+1)/2) THEN
                   RETURN TRUE
              ENDIF

together with the conventional interpretation of d/2 and (d+1)/2, the integer division. We will see this change makes the most sense as shown by the simple proposition below that characterizes the semantic of function A(G,s, t,d).


We have the following proposition.

Reachable(d): A(G,s,t,d) returns TRUE if and only the distance from s to t is less than or equal to d.

Let us prove the above proposition by induction on d.

The base case when d = 1 is trivial.

Suppose reachable(d) is true for all d <= n, where n>=1. Let check the case when d=n+1. There are two cases.

  • n+1 is even. Suppose n+1 = 2k. Checking the definition of function A, we can see that A(G,s,t, n+1) returns TRUE if and only if there is a vertex v such that both A(G,s,v, k) and A(G,v,t,k) return true, i.e., both the distance from s to v and the distance from v to t are less than or equal to k, thanks to the induction hypothesis since k <=n. That means the distance from s to t is less than or equal to 2k = n+1.
  • n+1 is odd. I will leave this case for you to check.

Proof is done.

The correctness of the algorithm is the correctness of reachable(|V(G)|), since there is path from s and t if and only if the distance from s to t is less than or equal to |V(G)|-1 (or |V(G)|, which is equivalent).


To verify that this algorithm can be very inefficient, we should find an example where it runs very slowly. We would like to choose a graph for which A(G,s,t,d) computes as much as possible and return as late as possible. How about graphs with no edges? Let D be a graph of 2^n vertices without an edge.

Claim: A(D,s,t,2^k) will call A(D,*,*,2^(k-1)) 2^(n+1) times.

Claim: A(D,s,t,2^n) will call A(D,*,*,1) (2^(n+1))^n=(2^n)^(n+1)=|V(D)|^(log |V(D)| +1) times.


I will let you contemplate why this algorithm is so inefficient.

$\endgroup$

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.