3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – utdiscant
    Sep 8, 2010 at 16:30

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Serge Gaspers
    Sep 8, 2010 at 15:46
  • $\begingroup$ Indeed. This stuff makes me start liking complexity theory :) $\endgroup$
    – jkff
    Sep 8, 2010 at 18:49
7
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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