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.
3
-
1$\begingroup$ It's called metric TSP. Searching under that term will find many proofs that it is NP-hard. $\endgroup$– D.W. ♦Commented Dec 12, 2019 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$– PatrickCommented Dec 12, 2019 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. ♦Commented Dec 12, 2019 at 1:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\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$– StevenCommented May 10, 2020 at 17:05