A basic question about approximation algorithms for the Traveling Salesman Problem

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?

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.

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.

• In the situation I described above, all of the Hamilton cycles of $G_1$ have the same value of $n$. So when you say "the 2-approximation algorithm will return some tour whose value is at most $2n$" that would mean that the algorithm returns a tour of value $n$. What I was confused about was the input to the problem. As you mention in your answer, the input must be a complete graph, and I didn't realize that. – Aaron Oct 30 '14 at 15:03
• In the situation you describe, the only tours whose value is at most $2n$ have value $n$, so yes, the algorithm will return a Hamilton cycle. But more generally it needn't be the case, and all you are guaranteed is that the algorithm returns some tour whose value is at most $2n$. – Yuval Filmus Oct 30 '14 at 15:05