Graph Algorithms

Question 1
As an Auror, 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]