Assignment 8 solution

You are on your honour to present your own work and acknowledge your sources.

 

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.