P/NP reduction (hamiltonian cycle to TSP)

Question

I have a P/NP question.

I have read that were any NP problem be found to have a polynomial time algorithm, then we can reduce any other NP problem to a form where we can use our first algorithm to solve the new NP problem in polynomial time as well.

I don't see why this is the case.

Example: Hamiltonian Cycle problem, and Traveling salesman.

Were I to find a polynomial time algorithm to determine the existence of a hamiltonian cycle in a graph, I still don't see how this could let me find a TSP tour in an upper bound of polynomial time. The amount of subgraphs we would have to iteratively check for a hamiltonian cycle is often exponential. It's typically impossible to create a single subgraph that contains all potential TSP tours under a given bound and would still only contain one hamiltonian circuit.

Answer 1

It's a bit more abstract than that. It is indeed not obvious at first to obtain a TSP tour by solving the Hamiltonian cycle problem - one thing to remember is that the problems in NP are decision problems.

The decision formulation of TSP is as follows: given a TSP instance $G$, is there a tour of length at most $k$?

This means that the reduction from TSP to Hamiltonian cycle would do this: it takes a TSP instance $G$ and constructs another graph $G'$ such that $G$ has a tour of length at most $k$ iff $G'$ is Hamiltonian. Here $G'$ might not even resemble $G$ at all, it just has to satisfy the above property. So $G'$ does not give you a tour - it just answers the yes/no question on the tour of length $k$ in $G$.

Suppose the answer is yes. To obtain an actual TSP tour of length at most $k$, one thing that can be done is to remove an edge $e$ from $G$ and re-run the same reduction. If the answer becomes 'no', it means that $e$ must be in the tour. If the answer is 'yes', it means you can delete $e$. You repeat for each edge one after another until you get the tour.

Answer 2

The Cook-Levin theorem establishes that Boolean Satisfiability (SAT) is NP-complete.

The usual way to prove NP completeness of a decision problem $P$ other than SAT is by reduction; that is, by exhibiting a polynomial algorithm that transforms instances of a known NP-complete problem $P'$ into "equivalent" instances of $P$. One then argues that a polynomial algorithm for $P$ would yield a polynomial algorithm for $P'$.

This process of proving NP-completeness by reduction produces a tree of decision problems at the root of which is SAT. For TSP and Hamiltonian Cycle (HC) the relevant part of the tree looks like this in most presentations:

$$ \text{SAT} \rightarrow \text{3SAT} \rightarrow \text{Vertex Cover} \rightarrow \text{HC} \rightarrow \text{TSP} \enspace. $$

For instance, this is the chain found in the venerable Garey and Johnson and in several popular textbooks. According to this path in the tree, it's easy to transform an instance of HC into a corresponding instance of TSP. However, the Cook-Levin theorem tells us that we can reduce TSP to SAT, and from there, through the series of reductions shown above, get to a corresponding instance of HC.

So the tree of explicit reductions used to prove completeness induces (through the Cook-Levin theorem) a directed graph that is strongly connected.

As pointed out by @ManuelLafond, the instance of HC one obtains at the end of this tour will not look immediately related to the original instance of TSP, but its size will be bounded by a polynomial in the size of the TSP instance, which is what matters.