transform traveling salesman problem into subgraph isomorphism problem

Question

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!

Answer 1

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:

1. 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.

2. 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.

3. 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.

Answer 2

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$.