Harry Potter, Grimaud Place to the ministry of magic.

Question 1 As an Author, Harry Potter needs to commute from his home at Number 12, Grimmauld Place to the ministry of magic. In order not to be seen by muggles, he can only use the portkeys and the muggle way of driving cars through the London road network, instead of flying on the broom. The portkeys are everyday objects that are enchanted with a fixed destination and just by touching them, one gets instantaneously teleported to the destination location. Harry has the road network with associated edge weights that capture the driving distance. He also knows of the location of the various portkeys, where they are and their destination. However, he can only use two portkeys in a single commute as otherwise he runs the risk of decomposing himself. Give an time algorithm to compute the shortest path from his home to the ministry that uses at most two portkeys. Here, is the number of locations/ intersections in the London road network (including the portkey locations) and is the number of roads between those locations/intersections. Argue its correctness as well as its asymptotic complexity. [25 marks] [Hint: Transform the graph instead of designing increasingly complex algorithms] Question 2 Define k-Clique to be the problem that considers a graph and an integer , and determines if there is a set of nodes, such that between any two nodes in , there is an edge in . (a) Show that -clique problem is in NP. [5 marks] (b) The independent set problem is to determine if there is an independent set of size . For a graph , we say is an independent set in G if there are no edges O(n log n + m) n m G = (V, E ) k S k S G k k G = (V, E ) S ⊆ V Page 1 of 3 between any two nodes in . We have shown that the problem of independent set is NP-hard. Reduce the independent set problem to the -Clique problem in order to show that -Clique is NP-hard. [15 marks] Question 3 Consider the following algorithm for computing the second shortest path between vertices and in an undirected graph . Either give a counter-example to show that this algorithm is incorrect or prove its correctness. [15 marks] Algorithm SecondShortestPath( ) Compute the first shortest path between and in Remove all edges in from to form Compute the shortest path between and in Return Question 4 The distance between two nodes in an unweighted graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance. The eccentricity of a node v is the maximum distance between v and any other node. The diameter of a graph is the maximum eccentricity of any node in the graph. Give a algorithm for this problem that returns a value that is between D/2 and D, if the actual diameter is D? [15 marks] Question 5 Here’s yet another minimum spanning tree algorithm: Algorithm 1 MST(G) 1: T := G 2: while T contains a cycle do 3: Choose an arbitrary cycle C in T 4: Remove the heaviest edge in C from T 5: end while 6: return T (a) Prove that this algorithm does indeed produce a minimum spanning tree of G. You may assume that G is connected and that there are no two edges in G that have the same weight. [15 marks] Note that this question is asking for a mathematically rigorous formal proof, similar to what you have been given in "Tutorial Solution: Question 2a Formal proof" part in the Brightspace section on Minimum spanning trees (b) Give an efficient way to implement this algorithm and argue its asymptotic complexity [10marks] S k k s t G G,s, t P1 s t G P1 G G′ P2 s t G′ P2 Θ(n + m) Page 2 of 3 Bonus Question You are a farmer and are considering purchasing an electric tractor. You have farms at different locations in the Irish countryside, roads connecting those farms and you want to be able to visit the farms to survey the ongoing agriculture work. On a full charge, the electric vehicle can go km. Since you can quickly charge at any of your farm, you are only concerned about the length of the longest road you have to traverse and whether or not it is smaller than km. If needed, you are willing to backtrack over a road in order to minimise the length of the longest road you will have to traverse. Of course, you can take longer detours through your farms to go from one farm to another as long as the maximum length of the road that you have to traverse is less than kms. Give an time algorithm to determine if it is possible to visit your farms in this way. Argue the correctness of your algorithm as well as its asymptotic complexity. [20 marks] Update: You can assume that and that the endpoints of the roads are the farms that you have.