Bottleneck TSP with MST

Question

There is a problem I don't know the answer too. The 3 approximation for the bottleneck TSP that involves first getting the MST. I have not been able to come up with the right "shortcut" method so far.

To be more specific.

The problem comes from Cormen's Introduction to Algorithms 3rd edition . The problem is

In the bottleneck traveling-salesman problem, we wish to find the hamiltonian cycle that minimizes the cost of the most costly edge in the cycle. Assuming that the cost function satisfies the triangle inequality, show that there exists a polynomial time approximation algorithm with approximation ratio 3 for this problem. (Hint:Show recursively that we can visit all the nodes in a bottleneck spanning tree, as discussed in Problem 23-3, exactly once by taking a full walk of the tree and skipping nodes, but without skipping more than two consecutive intermediate nodes. Show that the costliest edge in a bottleneck spanning tree has a cost that is at most the cost of the costliest edge in a bottleneck hamiltonian cycle.)

I can prove that the MST is also a bottleneck spanning tree, however when I search online and Google scholar for the step where we walk on the bottleneck spanning tree, all of the articles are on much better approximations, and I can't seem to find any reference to this type of argument online.

Answer 1

You need to prove by induction the following claim:

Let $T$ be a tree rooted at $r$ with at least two vertices. You can list the vertices of $T$ in a sequence such that the distance (in $T$) between two adjacent vertices (including the first and the last) is at most $3$, and furthermore the vertex following $r$ is adjacent to $r$ (in $T$).

(The induction is on the number of vertices.)

Given this, you argue as follows. Suppose that there is a Hamiltonian cycle with heaviest edge having weight $w$. Then there is a spanning tree whose heaviest edge has weight $w$. So the heaviest edge in the bottleneck spanning tree has weight at most $w$. Apply the claim to that tree, and consider the corresponding Hamiltonian cycle. Since the tree distance between adjacent vertices is at most $3$ and thanks to the triangle inequality, the heaviest edge in the resulting cycles weighs at most $3w$.