Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Why do you think that it is possible to transform traveling salesman problem into subgraph isomorphism problem? –  Boris Novikov Apr 7 '13 at 17:32
    
I read, that if you could solve one NP-complete problem in constant time, you can solve them all, so I think that all NP-complete problems are transferable to each other. –  Tomáš Šíma Apr 7 '13 at 17:34
    
I thought it went that if you could solve one NP-complete problem quickly, you could solve all NP problems quickly (that follows from the definition of NP-hard)? –  Julien Clancy Apr 7 '13 at 17:39
3  
If two problems are NP-complete, then you can solve one using at most a polynomial number of calls to a routine that solves the second. (So if you can do the second in constant time, you can do the first in polynomial time.) And note that you decide the existence of a Hamilton cycle in one call to a subgraph isomorphism routine, so the problem is to reduce TSP to Hamilton cycle, –  Chris Godsil Apr 7 '13 at 17:42
1  
@ChrisGodsil If I understand correctly a single call does suffice, but it requires a polynomial amount of precomputation, so it still isn't a constant time endeavour. –  Erick Wong Apr 7 '13 at 17:47

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
In order to do this, you must know the length and weights for the optimal Hamiltonian path.... –  N. S. Apr 16 '13 at 23:59
    
Isn't the length of TSP always $n$?!! (a Hamiltonian path of length $n$) –  Daniel Apr 23 '13 at 5:30
    
The TSP problem doesn't ask you to find ANY Hamiltonian path. You need to find a special one, namely the one with the minimal total weight/cost. If by length you mean the length of the path, then you are NOT solving the TSP problem. You need what you call the length to be the "optimal weight", but then you don't know this..... –  N. S. Apr 23 '13 at 14:41
    
oh, I see your point .... –  Daniel Apr 26 '13 at 20:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.