Theory of Computational Complexity, 2nd Edition

Theorem 2.25

TSP is NP-complete.

Proof

There is a simple reduction from HC to TSP: For any graph , we map it to a complete graph with the costs if , and if , and let . Then, it is clear that G has a Hamiltonian Circuit if and only if G^′ has a tour of total cost K.

Using the notion of polynomial-time Turing reducibility, it is not hard to show that the search problem of TSP that asks for the minimum-cost tour is equivalent to the above decision problem (see Exercise 2.18). Therefore, the search problem of TSP is also NP-hard. In the following, we show that the approximation to TSP is also NP-hard.

For each graph G with a cost function c on its edges, let denote the cost of ...