Description
1. [10 marks] Given a set P of n points in the plane a minimum Steiner tree is a tree that
connects the points of P and has minimum total Euclidean (i.e. L2) length. For example, for 3
points p1, p2, p3 forming an acute triangle, the minimum Steiner tree has leaves p1, p2, p3 plus a
node of degree 3 in the middle of the triangle at the Fermat point where the 3 edges form
angles of 120o
. (Look at Wikipedia for examples.) Prove that there is a polynomial time 2-
approximation algorithm for the minimum Steiner tree problem in the plane. In particular,
show that the minimum spanning tree of the points (using Euclidean distances as edge weights
in the complete graph) is a 2-approximation. Hint: refresh your memory on the 2
approximation algorithm for the Travelling Salesman
Problem or see [CLRS, section 35.2]
2. [10] Given a directed graph, G, represented by its adjacency matrix. (Let’s assume there are
no loops … i.e. no edges (i,i).)
a) [6 marks] Give an efficient algorithm to determine what pairs of nodes have directed paths
of length exactly n-1. Give the runtime of your method and justify this runtime. (Hint: think
first about what nodes are connected by paths of length 2.)
b) [4 marks] We know the Hamiltonian cycle problem is NP-Complete. The Hamiltonian path
problem, of having a path go though each node exactly once, is also NP-hard. Explain this
apparent anomaly, given that you have already given an efficient algorithm to find paths of
length n-1.
