The traveling salesman problem is NP-complete

[mathmari]

Hey! The traveling salesman problem is NP-complete.
Proof:
First, we have to prove that TSP belongs to NP. If we want to check a tour for credibility, we check that the tour contains each vertex once. Then we sum the total cost of the edges and finally we check if the cost is minimum. This can be completed in polynomial time thus TSP belongs to NP.
Secondly we prove that TSP is NP-hard. One way to prove this is to show that Hamiltonian cycle TSP (given that the Hamiltonian cycle problem is NP-complete). Assume G = (V, E) to be an instance of Hamiltonian cycle. An instance of TSP is then constructed. We create the complete graph = (V,≤ PG′ E′), where E′ = {(i, j):i, j ∈ V and i ≠ j. Thus, the cost function is defined as:

$$t(i,j)=\left\{\begin{matrix}
0, \text{ if } (i,j) \in E\\
1, \text{ if } (i,j) \notin E
\end{matrix}\right.$$Now suppose that a Hamiltonian cycle h exists in G. It is clear that the cost of each edge in h is 0
in G′ as each edge belongs to E. Therefore, h has a cost of 0 in G′ . Thus, if graph G has a
Hamiltonian cycle then graph G′ has a tour of 0 cost.
Conversely, we assume that G’ has a tour h’ of cost at most 0. The cost of edges in E’ are 0 and 1
by definition. So each edge must have a cost of 0 as the cost of h’ is 0. We conclude that h’
contains only edges in E.
So we have proven that G has a Hamiltonian cycle if and only if G’ has a tour of cost at most 0.
Thus TSP is NP-complete. Could you explain me the reduction?? (Wondering)

 

[Future Bruno]

Sure. The reduction is a process of transforming one problem into another problem with the intention of proving that the two problems are equivalent. In this case, we transform the Hamiltonian Cycle problem (which is known to be NP-complete) into the Traveling Salesman Problem (TSP). We do this by constructing a new graph, G', from the given graph, G. This new graph has the same vertices, V, as the given graph and it has edges between all of these vertices. We then assign a cost to each edge, so that edges in G have a cost of 0 and edges not in G have a cost of 1. Now, if there is a Hamiltonian cycle in the original graph G, then we can construct a tour in G' of cost 0, since the cost of each edge in the Hamiltonian cycle is 0. Conversely, if there is a tour in G' of cost 0, then the only way this can be achieved is if the tour only contains edges in G, meaning that there must be a Hamiltonian cycle in G. Therefore, we have shown that the Hamiltonian Cycle problem is equivalent to the Traveling Salesman Problem, thus demonstrating that TSP is NP-complete.