= Solution
Reduce the <Hamiltonian cycle> decision problem to the <metric travelling salesman problem>. Given a simple graph on $n\geq3$ vertices, form the complete graph with distance $1$ on original edges and distance $2$ on nonedges. These symmetric distances satisfy the <triangle inequality>, since a direct distance is at most $2$ and any two positive edge distances sum to at least $2$.
A tour has $n$ edges, each of cost at least $1$. It has cost at most $n$ exactly when every edge is an original graph edge, that is, exactly when the original graph has a <Hamiltonian cycle>. The construction and threshold are polynomial in the input size. Thus \b[the <metric travelling salesman problem> is <NP-hard>]; its rational-cost threshold version is also in <NP> because a tour is a polynomial-size certificate.
Allowing repeated vertex visits does not reduce the optimum for a complete metric instance. Given a closed walk visiting every vertex, keep the vertices in order of first appearance and shortcut the portions between them, including the final return. The <triangle inequality> makes the resulting Hamiltonian tour no more expensive. Conversely a Hamiltonian tour is an allowed closed walk. Hence the two optimal costs are equal, and \b[the repeated-visit metric version remains <NP-hard>]. If travel is described on a sparse graph, taking its shortest-path metric gives the corresponding closed-walk formulation rather than an easier exact problem.
Back to article page
