Travelling salesman problem

Remarks

The decision version is NP-complete, and the optimization version is NP-hard. Hardness follows from the Hamiltonian cycle problem. Given a graph $G$ on $n$ vertices, give weight $1$ to its edges and weight $2$ to the other pairs. Then $G$ has a Hamiltonian cycle exactly when some tour has length $n$. Trying all $(n-1)!/2$ tours solves the problem. The Held–Karp dynamic programming algorithm takes $O(n^2 2^n)$ steps. When $w$ satisfies the triangle inequality, Christofides' algorithm finds a tour at most $3/2$ times the optimum in polynomial time. Without the triangle inequality, no polynomial-time algorithm achieves any constant approximation factor unless $\mathrm{P} = \mathrm{NP}$.