CS 163, Spring 2012, Homework 6, due Thursday, May 24

1. Suppose that an undirected and weighted graph G has the property that its minimum spanning tree is a path.

1. How will the cycle found by Christofides' heuristic differ from this path?

2. In this case, is it always true that the cycle found by Christofides' heuristic is the optimal traveling salesman tour? If so, explain why; if not, draw a counterexample.

2. In the lecture we looked at two algorithms for finding the optimal solution to the traveling salesman problem: a brute force search algorithm that takes time O(n − 1)! on n-vertex graphs and a dynamic programming algorithm that takes time O(n2 × 2n).

1. Assuming the constant factors within the O-notation are the same for both algorithms, for which values of n will the brute force search be faster, and for which values of n will the dynamic program be faster?

2. Suppose more precisely that the brute force algorithm takes (n − 1)!/109 seconds and that the dynamic program takes (n2 × 2n) /109 seconds to run. You are willing to spend one hour of processing time to get an answer. What is the largest n for which each algorithm will run within that time limit?

3. Supposing that we store tour lengths as 64-bit floating point numbers, the dynamic programming algorithm needs 8n2n bytes of memory to store the intermediate results of the algorithm. For your answer in part b, how many bytes is that?

3. Draw a flow problem that is equivalent to finding a maximum matching in the bipartite graph shown below. You do not have to solve the flow problem.

4. In the following network, the vertices represent countries that might be involved in smuggling nuclear weapons from China to Iran, and the edge capacities represent how expensive it would be (in billions of dollars) to shut down all smuggling between the two countries connected by the edge. In this network, find a minimum cut separating China from Iran (representing the cheapest set of borders to target in order to prevent the weapons from getting to Iran) and a maximum flow with the same value as your minimum cut. For the flow you found, show also the residual graph.