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 ...

Start Free Trial

No credit card required