Let G V E be an undirected graph where V n and E m Suppos

Let G = (V, E) be an undirected graph where |V| = n and |E| = m. Suppose for two vertices u, v elementof G, we want to know if u and v are reachable from one another, i.e., if there exists a path in G between u and v. (a) It should be clear that we could use either DFS or BFS to answer this question; however, what is the worst-case space complexity of each of these approaches? Specifically, assume that each vertex is represented using theta (log n) bits. How many bits will you need to store in each algorithm in the worst case? Express your answer asymptotically (i.e., using theta (middot) notation). (b) Let us try to develop a more space-efficient approach. Consider the procedure EXISTS-PATH(a, b, k), which takes as parameters vertices a, b Element V, and returns true if there exists a path in G connecting a and b that has at most k edges; otherwise, it returns false. We can implement this function as follows: For k > 1, EXISTS-PATH(a, b, k) = V_ w Element V (EXISTS-PATH(a, w, [k/2]) Lambda EXISTS-PATH(w, b, k/2)) For k = 1, EXISTS-PATH (a, b, k) = true if and only if (a, b) Element E or a = b; otherwise false. In other words, EXISTS-PATH(a, b, k) returns true if and only if there exists some vertex w Element V such that there is a path from a to w that uses at most [k/21] edges, and a path from w to b that uses at most [k/2] edges. Now, to answer the reachability question for a particular pair of vertices u, v Element V, we simply return the result of EXISTS-PATH(u, v, n-1). First argue that this algorithm is correct. Next, bound the number of bits the algorithm needs to store in the worst case - give your answer in asymptotic notation. (As before, assume that vertices can be represented using Theta (log n) bits.)

Solution

Argument:

This algorithm is correct as its following divide and conquer approach and will recursively iterate till k =1

1. Divide the number of edges and pick a vertice is between the given points

2. Conquer the problem recursively by dividing the sub problems till it k = 1

3. Take intersection of both the sub problems and merge the recursively found solutions to get the path between a and b

Complexity:

1. In worst case (dense graph) space for edges = |V|(|V|-1) = O(V)^2

2. Space for vertices = theta(log n)

3. Space complexity of graph = O(V+E) = O(V + V^2)=O(V^2)=O((log n)^2)