= Solution
For the <metric travelling salesman problem>, a tour is a polynomial-size <complexity certificate>: list the vertices in cyclic visiting order. In <polynomial time> verify that every vertex occurs exactly once, add the encoded <integer> edge costs and compare the sum with the threshold. The certificate has $O(n\log n)$ bits, and addition uses a number of bits polynomial in the input length. If validity of the metric input is not treated as a promise, nonnegativity, symmetry and all triangle inequalities can also be checked in <polynomial time>. Therefore \b[the decision problem belongs to <NP>].
An evaluation algorithm immediately decides a threshold instance by computing the optimum and comparing it with $L$. Conversely, suppose there is a polynomial-time decision algorithm. The optimum is an <integer> in $[0,nM]$, where $M$ is the largest edge cost; any fixed cyclic ordering gives the upper bound. <Binary search> on this interval using threshold queries finds the exact minimum. It makes $O(\log(nM+1))$ queries, and every queried threshold has polynomial encoding length. Thus the time is polynomial in the bit length, even when $M$ is numerically large. Zero-cost and trivial small instances can be handled directly. Consequently
$$
\boxed{\text{Polynomial-time evaluation exists}\ \Longleftrightarrow\ \text{polynomial-time decision exists}.}
$$
This concerns the optimum value; constructing an optimal tour is the separate optimization task.
For the hardness reduction, start with an undirected graph $G$ on $n\ge3$ vertices and form the complete graph with costs
$$
c_{ij}=\begin{cases}1,&\{i,j\}\in E(G),\\2,&\{i,j\}\notin E(G),\end{cases}\qquad i\ne j.
$$
These costs satisfy the <triangle inequality>, since every direct cost is at most two and every two-edge path costs at least two. Set the threshold to $n$. Every tour has exactly $n$ edges, each costing at least one. Hence it has cost at most $n$ precisely when all its edges came from $G$, which is precisely the existence of a <Hamiltonian cycle> in $G$. The construction and threshold encoding are polynomial-time. Thus the assumed <NP-completeness> of the Hamiltonian circuit problem gives <NP-hardness> of metric TSP; together with its <NP> membership this proves \b[<NP-completeness> of metric TSP decision].
For the approximation, compute a <minimum spanning tree> $T$. Deleting any one edge of an optimal tour leaves a <spanning tree>, so nonnegative costs imply
$$
c(T)\le\operatorname{OPT}.
$$
Double every tree edge. The resulting connected multigraph has even degrees and hence an <Euler circuit>, of cost $2c(T)$. Traverse it and skip previously visited vertices, except for the final return to the start. Each skip replaces a path by its direct edge; repeated use of the <triangle inequality> shows that no replacement increases cost. The result is a tour visiting every vertex exactly once and satisfying
$$
\boxed{c(\text{returned tour})\le2c(T)\le2\operatorname{OPT}.}
$$
The Euler traversal and shortcutting take <polynomial time>, so the assumed polynomial-time MST routine supplies the requested <polynomial-time algorithm>. This is the <double-tree approximation for metric TSP>. In the relative-error convention, $c/\operatorname{OPT}-1\le1$ when the optimum is positive, explaining the printed term “1-approximation”; in the multiplicative convention it is a factor-two approximation. If the optimum is zero, the same bound forces the returned tour to have zero cost as well.
Back to article page
