Let G = (V. E) be an undirected graph with all edge weights equal to I. Let d(i, j) denote the length of the shortest path between i and j. Now, suppose we wish to answer queries from the user of the kind what is d for different u, One option is to compute answers to each query as it comes. This takes O (mn time using BFS, as the graph is unweighted. Another option is to solve the so-called All-Pairs-Shortest-Path (APSP) problem and store all the answers. This returns the answer in (1) time, but uses O(n2) additional memory which can be cumbersome for large graphs (think n 10 comon in real networks). The goal of this problem is to see if there is middle ground, if we allow an approzimation. The proposed algorithm does the following (pre-processing): choose a random subset S of vertices (the size is specified later). For each s E S, do a BFS and store the values d(s, u) for all u E V (query): at query time, given u, v, return minsesId(u, s) + d(v, s)) a) 2] Prove that for any choice of S, the value we output for a query is 2 d(u, v) (b) [3] Suppose we obtain S by randomly including every vertex of U with probability r/m. (Thus the expected size of S is r.) What are the expected pre-processing time and the memory usage of the algorithm? c7 Suppose that d(u, v) > 5n/r for some pair of vertices u, v. Prove that with probability>0.99, we obtain the right answer to the distance query. Hint: consider the shortest path from u to v and the vertices on it.] The moral is that if G is sparse, then by picking say rvn, we can do much better than APSP, and get right distance values for all the "long paths" with high probability. Let G = (V. E) be an undirected graph with all edge weights equal to I. Let d(i, j) denote the length of the shortest path between i and j. Now, suppose we wish to answer queries from the user of the kind what is d for different u, One option is to compute answers to each query as it comes. This takes O (mn time using BFS, as the graph is unweighted. Another option is to solve the so-called All-Pairs-Shortest-Path (APSP) problem and store all the answers. This returns the answer in (1) time, but uses O(n2) additional memory which can be cumbersome for large graphs (think n 10 comon in real networks). The goal of this problem is to see if there is middle ground, if we allow an approzimation. The proposed algorithm does the following (pre-processing): choose a random subset S of vertices (the size is specified later). For each s E S, do a BFS and store the values d(s, u) for all u E V (query): at query time, given u, v, return minsesId(u, s) + d(v, s)) a) 2] Prove that for any choice of S, the value we output for a query is 2 d(u, v) (b) [3] Suppose we obtain S by randomly including every vertex of U with probability r/m. (Thus the expected size of S is r.) What are the expected pre-processing time and the memory usage of the algorithm? c7 Suppose that d(u, v) > 5n/r for some pair of vertices u, v. Prove that with probability>0.99, we obtain the right answer to the distance query. Hint: consider the shortest path from u to v and the vertices on it.] The moral is that if G is sparse, then by picking say rvn, we can do much better than APSP, and get right distance values for all the "long paths" with high probability