Hamiltonian Cycles

The Hamiltonian cycle problem is one of the most famous in graph theory. It seeks a tour that visits each vertex of a given graph exactly once. It has a long history and many applications, as discussed in Section . Formally, it is defined:  

Input: An unweighted graph G.

Output: Does there exist a simple tour that visits each vertex of G without repetition? Hamiltonian cycle has some obvious similarity to the traveling salesman problem. Both problems ask for a tour to visit each vertex exactly once. There are also differences between the two problems. TSP works on weighted graphs, while Hamiltonian cycle works on unweighted graphs. The following reduction from Hamiltonian cycle to traveling salesman shows that the similarities are greater than the differences:

HamiltonianCycle(G=(V,E))

		 Construct a complete weighted graph G'=(V',E') where V'=V.

		 n = |V|

		 for i = 1 to n do

		 		 for j = 1 to n do 
							if    then w(i,j) = 1 else w(i,j) = 2

			Return the answer to Traveling-Salesman(G',n).

The actual reduction is quite simple, with the translation from unweighted to weighted graph easily performed in linear time. Further, this translation is designed to ensure that the answers of the two problems will be identical. If the graph G has a Hamiltonian cycle , then this exact same tour will correspond to n edges in E', each with weight 1. Therefore, this gives a TSP tour of G' of weight exactly n. If G does not have a Hamiltonian cycle, then there can be no such TSP tour in G', because the only way to get a tour of cost n in G would be to use only edges of weight 1, which implies a Hamiltonian cycle in G.

This reduction is both efficient and truth preserving. A fast algorithm for TSP would imply a fast algorithm for Hamiltonian cycle, while a hardness proof for Hamiltonian cycle would imply that TSP is hard. Since the latter is the case, this reduction shows that TSP is hard, at least as hard as Hamiltonian cycle.