A basic question about approximation algorithms for the Traveling Salesman Problem

Question

Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard. The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be decided. This standard proof is discussed in many places including accepted answers on cs.stackexchange here and here.

Briefly, the standard proof for $k=2$ works as follows. Suppose a graph $G$ with $n$ vertices is given as input to the Hamilton Cycle problem. We create a weighted complete graph $H$ with the same $n$ vertices as follows: The edges in $G$ are given weight 1, and the added edges are given a large weight, say $n+2$. Notice that every Hamilton cycle in $H$ either has total weight $n$, or at least $(n-1) + (n+2) = 2n+1$. This gap allows a 2-approximation algorithm for TSP to answer the decision problem. More specifically, if $G$ has a Hamilton Cycle, then the 2-approximation algorithm must return the value $n$ since the other Hamilton cycles have total weight $>= 2n+1$. On the other hand, if $G$ does not have a Hamilton cycle, then the 2-approximation algorithm will return a value larger than $n$.

I'm uncertain about something even more basic. What would a 2-approximation algorithm return if we did not add the edges of weight $2n+1$? In other words, suppose we take graph $G$ and create a weighted graph $G_1$ by assigning weight 1 to each edge in $G$, and we do not add any new edges. In this case, the Hamilton cycles in $G_1$ (if any) all have total weight $n$, and they all correspond to Hamilton cycles in $G$. There is no gap in the total weights of the Hamilton cycles.

What exactly would the 2-approximation algorithm return if $G$ has a Hamilton cycle? And what if $G$ does not have a Hamilton cycle?

Answer 1

The misunderstanding comes from two variations of the TSP problem:

1. The input graph is complete.
2. The input graph is arbitrary.

The standard proof above must assume the first variation of TSP. Thus, there is no k-approximation algorithm for the first variation unless $P=NP$. The same result then follows for the second variation due to the fact that the second variation generalizes the first variation.

To answer the question directly: The input to the TSP variation in question must be a complete graph.

Note: The Wikipedia article states the following: Often, the model is a complete graph (i.e. each pair of vertices is connected by an edge). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.

Answer 2

The 2-approximation algorithm returns a TSP (cyclic) tour whose value is at most twice the optimal value. The input to the algorithm is a complete weighted graph – you need to specify a weight for each edge. If there is a Hamilton cycle, which has the minimal value $n$, the a 2-approximation algorithm will return some tour whose value is at most $2n$. It could return a Hamilton cycle. Or it could return something else. It depends on the algorithm and on the graph. If there is no Hamilton cycle, and the minimal TSP tour has weight $m$, then the algorithm will return some tour of weight at most $2m$.

The construction you describe ensures that a 2-approximation algorithm will return a Hamilton cycle if there is one; if there isn't, it of course would return any. So looking at the output, we could know whether the original graph contained a Hamilton cycle. In fact, it is enough to know only the weight of the cycle returned by the 2-approximation algorithm.

Answer 3

In the "Hamilton cycle" problem, two nodes are either connected or not connected. Let's replace this with a "Travelling salesman" instance, where any two connected nodes have a distance of 1, and any two unconnected nodes have a distance of 2. If there is a Hamilton cycle, then the TSP instance has a solution of length n. If there is no Hamilton cycle, then the TSP instance must use some connection of length 2 instead of 1, so the optimal route has a length ≥ n+1.

This makes it easy to check if there is a Hamilton graph: Create and solve the TSP instance, then check if the optimal solution had a length n or a length ≥ n+1. And that proves that TSP is NP-complete, because it can be used to solve instance of the NP-complete "Hamilton cycle" problem.

Now there is an obvious way to show that "finding an approximation that is at most k > 1 times longer than the optimal" is NP-hard:

Take a "Hamilton cycle" instance. Create a TSP instance where nodes have a distance of 1 or 1 + M. We'll figure out M. The optimal solution of the TSP problem has a length of exactly n if there is a Hamilton cycle, and at least n + M if there is no Hamilton cycle. Your approximation algorithm will find a solution of length ≤ n * K in the first case. In the second case, there is no solution shorter than n + M, so your approximation algorithm will find a solution of length ≥ n + M. Being a K-approximation, it might actually find a solution of length K * (n + M), but n + M is the minimum.

If we choose M > n * (K - 1), then the solution will have length ≤ n * K in the first case, and length > n * K in the second case. So by finding a K-approximation to the optimal tour, we can check its length and figure out whether there was a Hamilton cycle or not. So for any K > 1, being able to find K approximations solves an NP-complete problem and is therefore at least as hard as solving the NP-complete problem.