Understanding the reduction from Hamiltonian cycle to the traveling salesman problems

Question

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 is reducible to 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,\leq PG' E')$, where $E' = \{(i, j):i, j ∈ V\}$ and $i \neq 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??

Answer 1

Assuming for now on you deal with the decision problem of the TSP, which is:

Given as input a weighted undirected graph $G=(V,E, \omega)$ and at bound $C$, is there a Hamiltonian cycle in G whose weight is at most C?

This is easily seen to be in NP (contrary to the optimization version you state in your question, which, if shown to be in NP, would yield a lot of interesting consequences). The reduction goes as follows: assuming the existence of an efficient algorithm $A$ for the Decision-TSP, you can take any instance $G=(V,E)$ for the Hamiltonian cycle problem and convert it into an instance $G^\prime=(V,E^\prime=V\times V, \omega), C=0$ of Decision-TSP as above (defining the cost function $\omega$ by $\forall e\in E^\prime, \omega(e) = \mathbb{1}_{e\in E}$), such that

• if there is a Hamiltonian cycle in $G$, then $A$ will return "yes" on input $(G^\prime,C)$;
• if there is no Hamiltonian cycle in $G$, then the minimum Hamiltonian cycle in $G^\prime$ has cost at least $1$, and thus $A$ will return "no" on input $(G^\prime,C)$.

Therefore, $A$ can be used to solve the Hamiltonian cycle problem, efficiently (since for any $G$, $G^\prime$ can be computed efficiently and running $A$ on $(G^\prime,C)$ is efficient as well.