Mapping Problems to Prove TSP Solves HCP

[STEMucator]

Homework Statement

I wasn't sure where to post this in particular, so I apologize if this is in the wrong section.

I've been getting interested in the topic of problem mapping lately. I came across this problem while reading and I'm not quite sure if I have the right idea or not.

The Question :

A problem mapping means to create an instance of one problem out of the details (or data)
of another. Suppose you wanted to prove that a solution to the Traveling Salesman Problem would provide a solution to the Hamilton Cycle problem.

What is the correct mapping to use given the current information?

Homework Equations

Traveling Salesmen Problem ( TSP ) : http://gyazo.com/8944e64b668d3ea898662b083450d3d5

Hamiltonian Cycle Problem ( HCP ) : http://gyazo.com/865cb36a67f72cbd9db71913e1a4e076

The Attempt at a Solution

Well, the way I thought about this was to recognize the important details of the problems and create a map from one problem to the other. The reason this would work is because we already have a solution to one of the problems, namely the TSP ( Barring its computational limits which are exponential, i.e $2^n$ ).

So first things first. I map the cities to the nodes so $C = V$.

Now I need a way to tell the distances between the cities, but since I'm trying to map the problem, it reduces to finding distances between nodes. Suppose I denote this distance by $d_{i,j} ≥ 0$. The distance between cities is zero only when we are already at the destination of course.

So presume we have to travel some $n > 0$ number of nodes to reach our destination, and we have a distance function $d(v_i, v_j)$ which can tell the distance between two vertices which depend on $i$ and $j$.

Let :

$d(v_i, v_j) = 1$ if $v_i, v_j \in E$.
$d(v_i, v_j) = 2$ if $v_i, v_j \notin E$.

We can now travel along each node and find a path with a positive distance to the destination.

If the minimum length found from the start to the destination is ≤ n, then the set of cities has a Hamilton Cycle, otherwise it does not.

So the proper mapping is :

$C = V$
$d(v_i, v_j) = 1$ if $v_i, v_j \in E$.
$d(v_i, v_j) = 2$ if $v_i, v_j \notin E$.
$B = n$

 

[haruspex]

That all seems reasonable.

 

[Ray Vickson]

Homework Statement

I wasn't sure where to post this in particular, so I apologize if this is in the wrong section.

I've been getting interested in the topic of problem mapping lately. I came across this problem while reading and I'm not quite sure if I have the right idea or not.

The Question :

A problem mapping means to create an instance of one problem out of the details (or data)
of another. Suppose you wanted to prove that a solution to the Traveling Salesman Problem would provide a solution to the Hamilton Cycle problem.

What is the correct mapping to use given the current information?

Homework Equations

Traveling Salesmen Problem ( TSP ) : http://gyazo.com/8944e64b668d3ea898662b083450d3d5

Hamiltonian Cycle Problem ( HCP ) : http://gyazo.com/865cb36a67f72cbd9db71913e1a4e076

The Attempt at a Solution

Well, the way I thought about this was to recognize the important details of the problems and create a map from one problem to the other. The reason this would work is because we already have a solution to one of the problems, namely the TSP ( Barring its computational limits which are exponential, i.e $2^n$ ).

So first things first. I map the cities to the nodes so $C = V$.

Now I need a way to tell the distances between the cities, but since I'm trying to map the problem, it reduces to finding distances between nodes. Suppose I denote this distance by $d_{i,j} ≥ 0$. The distance between cities is zero only when we are already at the destination of course.

So presume we have to travel some $n > 0$ number of nodes to reach our destination, and we have a distance function $d(v_i, v_j)$ which can tell the distance between two vertices which depend on $i$ and $j$.

Let :

$d(v_i, v_j) = 1$ if $v_i, v_j \in E$.
$d(v_i, v_j) = 2$ if $v_i, v_j \notin E$.

We can now travel along each node and find a path with a positive distance to the destination.

If the minimum length found from the start to the destination is ≤ n, then the set of cities has a Hamilton Cycle, otherwise it does not.

So the proper mapping is :

$C = V$
$d(v_i, v_j) = 1$ if $v_i, v_j \in E$.
$d(v_i, v_j) = 2$ if $v_i, v_j \notin E$.
$B = n$

All this is pretty standard, and is well-discussed in computational complexity textbooks. Hamiltonian cycle and TSP are two instances of NP-Complete problems, and so are each reducible (in polynomially-bounded transformations) from one to the other. A lot of this stuff is presented in the old classic "Computers and Intractability: A Guide to the Theory of NP-Completeness", by M.R. Garey and D.S. Johnson, Freeman (1979). Or, you can Google "NP-Complete".