Linking HAM and TSP

Take the decision problem: Given a TSP instance, is the optimal tour less than some given size C? It is in NP...

We can reduce HAM to this. Given an n-node graph G=(V,E), we generate a TSP instance by using the same set of nodes and setting D(u,v) = 1 if $(u,v)\in E$ and D(u,v) = 2 otherwise.

This TSP has a tour of size n if and only if G has a Hamiltonian circuit (otherwise it is at least n+1). So,x if we could solve TSP in polynomial time, we could solve HAM in polynomial time, and P would equal NP.


next up previous
Next: Dealing with NP-Completeness Up: TRAVELING SALESPERSON PROBLEM Previous: Hardness of HAM