triangle inequality TSP is NP-complete? I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric TSP problem. So, I wonder how to start a basic approach to prove triangle inequality TSP is NP-complete.
If you accept a proof that TSP without triangular equation is NP-complete then it is easy: If you take an instance of "TSP without triangular equation", then you just add a large enough constant to each edge to get the triangular equation, solve it as an instance of "TSP with triangular equation", and that solves your original problem.