Answer Happy

Problem 5. [25pts] [Remote Tenuous] Let G be a connected and undirected graph on n vertices and m edges. The distance d(u, v) between two vertices u and u in G is defined as the number of edges in a shortest path between the two vertices. The vertices u, v in G are said to: 1. form a remote pair if d(u, v) > 2. form a tenuous pair if there exists a vertex r {u, v} in G such that the graph G - obtained by deleting z from G contains no path between u and v. The main question has the following two parts: a. Give a modification of BFS algorithm that takes the adjacency list of graph G and a vertex u as the input, and outputs whether there exists a vertex v such that (u, v) forms a remote tenuous pair (that is, (u, v) is remote pair, as well as tenuous pair). Moreover, if there exists a v such that {u, v} is a remote tenuous pair, then the algorithm must output v and another vertex r {u,v} such that G - has no path between u and v. [15pts] b. Prove the correctness of your algorithm, and show that it works in O(n+m) time. [10pts] OR If you find the above problem too hard, then attempt the following simpler version for fewer marks to score: a*. Give a modification of BFS algorithm that takes the adjacency list of graph G and a vertex u as the input and outputs a vertex v such that {u, v} forms a remote pair. Note that we do not demand {u, v} to be a tenuous pair. [5pts] b*. Prove that your algorithm is correct and runs in O(n + m) time. [5pts]