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') whereV'=V.

n= |V|for

i= 1 tondofor

j= 1 tondo if thenw(i,j) = 1 elsew(i,j) = 2Return 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.

Mon Jun 2 23:33:50 EDT 1997