Travelling Salesman Problem is NP complete

The traveling salesman problem So you have given a graph G and I am asking does the graph having a tour of cost at most k So I hope all of you know the traveling salesman problem Okay That is the salesman has to travel to all the cities and suppose he is starting from here he has to travel all the cities and he has to come back to the starting point. and with minimum cost and he can visit a city only once But he has to visit all the cities and come back to the Starting point So if you consider

this graph you can say this is the minimum cost tour From S you go to this vertex from here and like This is the minimum cost tour of the graph and Our problem is we have to findout does the graph G has a tour of cost at most k So we cannot find this minimum cost tour in polynomial time So the traveling salesman problem Is an NP complete problem So we have to prove it So first we will prove it Traveling salesman problem belong to the class NP That is Suppose if you are given a sequence of verti

ces Then we will check whether these vertices belong to the graph That is whether these vertices form the edges of the graph or not and we will compute the total cost of the edges and check whether the sum is at most k So this verification we can do in Polynomial time So we can say that the traveling salesman problem is a NP problem Now we have to prove that the traveling salesman problem is a NP hard problem For that We will reduce the Known NP hard problem that is Hamiltonian cycle problem To

the traveling salesman problem So The Hamiltonian cycle problem and traveling salesman problem are almost same Hamiltonian cycle means the cycle that contain every vertex of the graph. In traveling salesman problem also Salesman has to travel to every vertices Then come back to the starting point So here we will have a starting point But Hamiltonian considered this as a cycle and cycle does not have a starting point So we can easily convert the Hamiltonian cycle problem to traveling salesman pro

blem That is let G=(V,E) be an instance of Hamiltonian cycle This is an instance of Hamiltonian cycle Not the instance of graph and an instance of traveling salesman problem can be constructed from here by adding the edges and defining the cost to this edges I will set the cost of all edges in the Hamiltonian cycle to zero and all other edges that are not in Hamiltonian cycle will given a cost 1 and The graph G has a Hamiltonian cycle if and only if G dash Tour of at most Tour of cost at most 0.

That is G dash has now a tour of cost 0 and this reduction can be done in polynomial time So we reduced the Hamiltonian cycle problem to traveling salesman problem actually both are same and we know we have already proved that the Hamiltonian cycle problem is a NP hard problem So the traveling salesman problem is also an NP hard problem and it is a NP problem, we have proved it here So since traveling salesman problem is both NP hard and NP complete we can say sorry NP hard and NP we can say th

is problem is a NP complete problem