transform traveling salesman problem into subgraph isomorphism problem Lets say, I could solve subgraph isomorphism problem
in constant time.
How could I use this to solve traveling salesman problem?
aka... how to transform traveling salesman problem into subgraph isomorphism problem?
Thanks for help!
 A: 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:


*

*Every vertex (city) in $T$ is represented in $G$ as a linear segment of $\max + 1$ vertices and $\max$ edges, where $\max$ is the longest distance between any two cities.

*Every edge (path between two cities) in $T$ is represented in $G$ by two separate linear segments of $d$ vertices and $d+1$ edges, where $d$ is the distance between the two cities.

*For every pair of connected cities in $T$, connect the ends of the corresponding vertex segments in $G$ using the two edge segments that correspond to the path.
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.
A: 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$. 
