Problem Set #3, CS 255, due April 10, 2006

Final version

Exercise 34.5-2. You needn't show that the problem is in NP, but you should state how you decided on the definition of the polynomial-time transformation function that you used in your solution.
The APPROX-TSP-TOUR algorithm of Cormen et al, p. 1028, is incompletely specified, since line 3 does not say where the tree walk should start, or which successor vertex is to be chosen if there is more than one possibility. The undirected graph with vertices {0,1,2,3,4,5} and adjacency matrix below satisfies the triangle inequality condition. For this graph:
1. Find the minimum-cost spanning tree. Give the edges and the overall cost.
2. What tour is given by the algorithm, assuming that the tree walk is to start at vertex 0, and that unvisited successors of a given vertex are to be considered in numerical order? What is the cost of this tour?
3. Show that starting the tree walk at a different vertex, and keeping the same policy for visiting successors, can give a cheaper tour than starting at vertex 0.
4. Show that even if the tree walk starts at vertex 0, allowing unvisited successor nodes to be visited in an order different than numerical order can give a cheaper tour than requiring them to be considered in numerical order.
5. We have shown that considering several tours in the context of the APPROX-TSP-TOUR algorithm can give a better approximate solution than considering just one. Suppose that we require the algorithm to consider all possible starting points, and to consider unvisited successor vertices in all possible orders. How many tours will be considered in the worst case by this version of the algorithm?
```
       0  14  10  14  20  31
      14   0  22  20  31  40
      10  22   0  10  10  22
      14  20  10   0  14  20
      20  31  10  14   0  14
      31  40  22  20  14   0
```