Proving correctness of inefficient algorithm - Path between two vertices

Question

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!

Answer 1

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.