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.

  • 1
    $\begingroup$ It's called metric TSP. Searching under that term will find many proofs that it is NP-hard. $\endgroup$ – D.W. Dec 12 '19 at 0:05
  • $\begingroup$ Thanks, I had read the proofs but I don't think I understand it, basically they are providing short proofs, but it's similar to original reduction. So, referring to proofs, Instead of setting all edge in G to cost 0, and for all edge not in G to cost 1, they simply set all edge in G to cost 1 and all edge not in G to cost 2. But I'm confused how does this satisfied triangle inequality by increasing cost by 1. $\endgroup$ – Patrick Dec 12 '19 at 1:06
  • 4
    $\begingroup$ Please mention in the question what you've read, and what parts you did understand, and which is the first part you didn't understand. Otherwise, I worry we'll just repeat one of those proofs and then you'll say you didn't understand that either. Instead of leaving clarifications in the comments, please edit your question to expand on these points and provide more background and context about what you already understand and what you're struggling with. $\endgroup$ – D.W. Dec 12 '19 at 1:41

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.

| cite | improve this answer | |
  • $\begingroup$ And if @Patrick doesn't accept that (non necessarily metric) TSP is NP-Complete, an easy argument is that (the decision version) of TSP is a generalization of Hamiltonian cycle. $\endgroup$ – Steven May 10 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.