<p>First, you'd find the path length by binary search on the result of the decision problem.
Then you'd take an arbitrary node and for each edge, check (again with the decision problem) whether a path exists with that length and containing that particular edge. And so on until you've found the whole cyclic path.
Here you'd just need to be able to use the decision problem to test whether a path with given length exists, containing a particular edge, but I'm sure that must not be harder than the original decision problem.</p>

CC BY-SA 2.5
2010-09-08T15:46:24.170Z
Note that the original decision problem can be used to decide whether there is a shortest tour containing a given edge. Hint: modify the weight of the edge.
Serge Gaspers
CC BY-SA 2.5
2010-09-08T18:49:56.110Z
Indeed. This stuff makes me start liking complexity theory :)
jkff
CC BY-SA 2.5
2010-09-08T15:10:29.193Z
2010-09-08T15:10:29.193Z
jkff
<p>I'm not sure if we should be answering such questions, since it is at the level of a homework question, and not a research level question. So instead I'll just give a hint to the OP so the OP can figure out the answer with some effort. (Other posters may choose to give out the explicit solution if they wish, of course.)</p>

<p>The concept you refer to, i.e., reducing the search problem (or optimization problem) to the decision problem, is called self-reducibility. It is known that all NP-complete problems, and some others like Graph Isomorphism have this property. See <a href="http://www.cs.tau.ac.il/~safra/ACT/Lecture1.ppt">this powerpoint presentation</a> on self-reducibility. It explains in detail how SAT, GI and NP-complete problems in general can be shown to be self-reducible.</p>

<p>If you read those notes and understand those examples, you should be able to do the same for TSP using similar ideas.  Hope that helps.</p>

CC BY-SA 2.5
2010-09-08T15:09:44.753Z
2010-09-08T15:09:44.753Z
Robin Kothari
<p>Given an oracle for solving the decision version of TSP, how would I use this to solve the optimization version of TSP.</p>

<p>This is not a homework assignment, but of general interest. I have been trying to find a place with examples of these types of reductions.</p>

CC BY-SA 2.5
2010-09-08T16:30:39.513Z
This questing was actually related to another problem:

Given n cups of the same height, stack them in height h. If cup c_j is put into cup g_i let d_ij be the amount (height) of c_j above the rim of c_i.

I found that this problem looks like a directed version of travelling salesman. I have solved the problem now.
utdiscant
<np-hardness><reductions><oracles>
Using decision version of TSP to solve optimization version
utdiscant
# Using decision version of TSP to solve optimization version

(Asked by: username_0 on 2010-09-08)

Given an oracle for solving the decision version of TSP, how would I use this to solve the optimization version of TSP.

This is not a homework assignment, but of general interest. I have been trying to find a place with examples of these types of reductions.

**Tags:** np-hardness, reductions, oracles
> **Comments:**
> **username_0**: This questing was actually related to another problem:  Given n cups of the same height, stack them in height h. If cup c_j is put into cup g_i let d_ij be the amount (height) of c_j above the rim of c_i.  I found that this problem looks like a directed version of travelling salesman. I have solved the problem now.  

---

## 2 answers

### Answer by username_1 on 2010-09-08. Score: 3 | Accepted answer

First, you'd find the path length by binary search on the result of the decision problem.
Then you'd take an arbitrary node and for each edge, check (again with the decision problem) whether a path exists with that length and containing that particular edge. And so on until you've found the whole cyclic path.
Here you'd just need to be able to use the decision problem to test whether a path with given length exists, containing a particular edge, but I'm sure that must not be harder than the original decision problem.

> **Comments:**
> **username_2**: Note that the original decision problem can be used to decide whether there is a shortest tour containing a given edge. Hint: modify the weight of the edge.  
> **username_1**: Indeed. This stuff makes me start liking complexity theory :)  

---

### Answer by username_3 on 2010-09-08. Score: 7

I'm not sure if we should be answering such questions, since it is at the level of a homework question, and not a research level question. So instead I'll just give a hint to the OP so the OP can figure out the answer with some effort. (Other posters may choose to give out the explicit solution if they wish, of course.)

The concept you refer to, i.e., reducing the search problem (or optimization problem) to the decision problem, is called self-reducibility. It is known that all NP-complete problems, and some others like Graph Isomorphism have this property. See [this powerpoint presentation](http://www.cs.tau.ac.il/~safra/ACT/Lecture1.ppt) on self-reducibility. It explains in detail how SAT, GI and NP-complete problems in general can be shown to be self-reducible.

If you read those notes and understand those examples, you should be able to do the same for TSP using similar ideas. Hope that helps.


---

