Homework 3 COMS 311 Points: 100
1
1. There are n tennis players. There are m-pairs among these players who are bitter rivals of each other. Write an algorithm which checks whether the players can be arranged in two groups such that rival players are in separate groups; and if the check is successful, then your algorithm also outputs the two groups. Derive the runtime of your algorithm.
Ans. Consider an undirected graph G = (V,E) where each player is a vertex, and place an edge between players x and y, if they are rivals. Now, the goal is to partition V into two sets L and R such that there is no edge among vertices of L and there are no edges among vertices of R. Only edges allowed are the edges from a vertex in L to vertex in R. This will ensure that for any two rivals x and y, one of them is in L and the other in R. Thus the problem is to check whether the G is a bi-partite graph or not. We have seen an algorithm that checks whether a graph is bi-partite or not and if it is bi-partite, then outputs the partition of the vertex set. The run time of this algorithm is O(m + n).
2. Given an undirected connected graph G = (V,E), write an algorithm to determine whether there exists a cycle in the graph. Derive the runtime of your algorithm.
Ans. Main observation is that if an undirected graph is connected, then it has a cycle if and only if the number of edges if at least n. However if the graph is not connected, then it is possible that the graph has fewer than n edges and still has a cycle. However, consider a connected component of an undirected graph, if the connected component has l vertices, and has at least l edges, then that component has a cycle. This suggests the following algorithm: Compute the connected components of the undirected graph, for each component compute the number of vertices and edges. If there is a connected component where number of edges is at least the number of vertices in it, then the graph has a cycle. Otherwise, the graph does not have a cycle. We have seen BFS based algorithm, that computes connected components of a graph. The total runtime is O(m + n).
3. Given an undirected connected graph, we define the diameter of the graph as the length of the longest shortest path between any two vertices in the graph. In other words, in a graph with n vertices {v0, v1, . . . , vn−1}, if the shortest path between the vertex pair vi, vj is denoted by πij, then the diameter of the the graph is maxi∈[0,n−1],j∈[0,n−1](|πij|). Write an algorithm that determines the diameter of an undirected connected cycle-free graph. Derive the runtime of your algorithm.
Ans. To compute the diameter, we need to compute the length of the shortest path from every vertex x to every other vertex y and the maximum of all the lengths. We can use BFS to compute the length of the shortest paths. Recall that if we perform BFS from x, a vertex in layer Li is at distance from i to x and the BFS stops by constructing l layers then the furthest vertex from x is at distance l. Thus suggests the following algorithm.
(a) Input G = (V, E). (b) d=0.
(c) For every x ∈ V
• Perform BFS from x, ad let l be the number of layers constructed. • Ifl>d,thend=l.
(d) Output d.
2
Time take by BFS is O(m + n) and since we are doing n BFS computations, the time taken is O(n(m + n)).
4. Let G = (V, E) is a directed graph representing the road network of the village Totorum. The roads are one-way represented by directed edges and are of equal length L; each house in the village is represented by the nodes in the graph. Every day, the village doctor visits every house in the graph. For this, the doctor does the following
for every house v in the village
the doctor takes the shortest path from her residence to v
the doctor takes the shortest path from v to her residence
Determine the total distance traveled by the doctor every day. (Assume every house can be reached from from the doctor’s residence)
Ans. We will give an algorithm that gets a directed graph G = (V, E) and a vertex s at which the doctors resides and compute the total distance travelled by the doctor. For this, we need to compute the following: For every vertex x, the length of the shortest path from s to x and the length of the shortest path from x to s. Since each edge length equals L, the length of the shortest path between two vertices is the number of edges in the shortest path multiplied by L. Recall that if we perform BFS starting from s, the every vertex in layer i is at distance i from s. Thus we can comput ethe length of the shortest path from s to every vertex x by doing BFS. Now the goal is to compute the length of the shortest path from x to s, for every vertex x. This can be done by considering the reverse graph of G. Let Gr = (V,E′), where thereisanedgefromatobinE′ ifandonlyifthereisanedgefrombtoa. Notethata shortest path from a to b in G′ yields a shortest path from b to a in G (by reversing the edges of teh shortest path). Thus we can compute the shortest paths from x to s (for every x), by doing BFS from s in G′. This suggests the following algorithm:
(a) Input: G = (V, E), s.
(b) Create two arrays A and B. A[v] holds the length of the shortest path from s to v, and
B[v] holds the length of the shortest path from v to s.
(c) Perform BFS from s while computing layers. For every v ∈ Li, set A[v] = i × L.
(d) Compute Gr.
(e) Perform BFS from s in Gr while computing layere. For every v ∈ Li, set B[v] = i × L.
(f) Compute the sum of all elements in arrays A and B and output the sum.
Time taken for each BFS is O(m + n), time taken to compute Gr is O(m + n) and the time taken to sum the arrays is O(n). Thus the total time taken is O(m + n).
5. Suppose that an n-node undirected graph G = (V,E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all paths between s and t. Write an algorithm to find such a v. Derive the runtime of your algorithm.
Ans. Perform BFS from the vertex s and construct layers. Since the t is at a distance more than n/2, the vertex t must lie in a layer number l where l > n/2. Thus there must exist
3
a layer i, 1 ≤ i < l that has only one vertex. Otherwise the total number of vertices would be more than n. Since the graph is undirected, there can not be an edge between layers who layer numbers differ by more than 1. Thus removing the layer Li, which contains only one vertex, will disconnect s from t. 4