Lets say, I could solve subgraph isomorphism problem in constant time.
How could I use this to solve traveling salesman problem?
Thanks for help!
|show 3 more comments|
When reducing one NP-complete problem to another the general procedure is to construct gadgets in the target problem that mimic constraint features of the source problem and then use those gadgets to construct a target problem instance that has a solution only if the source problem instance has a solution.
In this case the source problem is traveling salesman, where we're given a list of cities and distances between them and are asked if there is a tour of the cities that covers less than some distance $k$. We must somehow simulate the distances and connectivity in such a way that a subgraph isomorphism solution tells us whether there is a short enough tour.
To do this, convert the traveling salesman graph $T$ to a new graph $G$ as follows:
To determine whether there is a tour of distance $k$ in $T$, ask the subgraph isomorphism oracle if there is a simple closed loop of length $n \cdot (\max + 1) + k$ vertices in $G$, where $n$ is the number of cities in $T$. To determine if there is a tour with a distance less than $k$, iteratively ask the oracle if loops exist of length $n \cdot (\max + 1) + 1$ through $n \cdot (\max + 1) + k - 1$; if the oracle answers "no" to all the queries, then no such tour of $T$ exists.
The requirement that the oracle find a simple loop ensures that the solution represents a tour (the trip returns to its origin) and that no city is visited twice. The requirement that the loop length be at least $n \cdot (\max + 1)$ guarantees that any solution found will represent a path that visits all the cities, as no graph can be long enough if one of the intentionally large vertex segments is left out.
This construction is a Cook reduction of traveling salesman to subgraph isomorphism. I don't know of a Karp reduction.
The answer is simple: you have a graph $G$ and want to find a Hamiltonian cycle of length $n$. Create a cycle of length $n$ and call it $H$. Now if $subgraph(G,H)$ gives you positive answer, your graph has a Hamiltonian cycle of length $n$.