CS46 — Homework 9


Due Thursday 2 May at start of class
Starting files are available from my public cs46 folder 
cd ~/cs46/
cp examples/homework/hw09.tex homework/
You may work with a partner and submit a common solution on this homework.
In lab practice
  1. Show VERTEX-COVER is NP-Complete. Note that INDEPENDENT-SET, CLIQUE, and 3-COLOR are NP-Complete. Pick the proper reduction
  2. TSP is NP-Complete under most assumptions. In general, the weights $d_{ij}$ do not need to satisfy the triangle inequality. The triangle inequality states $d_{ij} \leq d_{ik} + d_{kj}$.
    1. Give a small example of a TSP instance using one of the constructions from class that does not satisfy the triangle inequality.
    2. Argue that replacing $d_{ij}$ with $d^{'}_{ij} = d_{ij}+W$ for some fixed weight $W > 0$ does not change the optimal solution for TSP
    3. Show that for any instance of TSP that does not satisfy the triangle inequality can be converted into a instance that does satisfy the triangle inequality. This conversion can be done in polynomial time by choosing an appropriate value for $W$. What is this value?
  3. Considering the following approximation algorithm for TSP, assuming the weights obey the triangle inequality. 
    pick an arbitrary vertex v
compute the Minimum Spanning Tree T of G rooted at v
compute the Pre-Order Traversal L of T
return the Hamiltonian Cycle of L
    1. Show that the algorithm computes a valid tour
    2. Show that the algorithm runs in polynomial time
    3. Show that removing any edge from an optimal tour results in a tree. Obtain a lower bound for the cost of the optimal tour based on the cost of the minimum spanning tree
    4. Show that you can construct a path from the root $v$ back to $v$ that visits traverses each edge of the minimum spanning tree twice. Use the pre-order traversal to guide the path. What is the cost of this path?
    5. Show that the approximate TSP algorithm cost is no more than the cost of the path in the previous step. Use the triangle inequality in your proof. What is the approximation factor of this algorithm?
  4. Question 3 shows that you can get an $\varepsilon$-approximation for TSP instances that obey the triangle inequality. Question 2 says any instance of TSP that does not obey the triangle inequality can be converted to one that does. In class we said general TSP is inapproximable. What is going on?