In my studying of NP problems, repeated references are made to the fact that you can reduce any optimization problem to a decision problem.(ie if you can solve the decision problem in polynomial time, you can solve the optimization problem in polynomial time). But I’ve never seen an actual example of this. The texts always just wave their hands and mumble something about binary search. But for the life of me, I can’t figure it out.
Take, for example, the travelling salesman problem. The optimization problem is to find the shortest path that visits every node. The decision problem is: does there exist a path of length no more than d? Ok, so using binary search I can easily find the length of the shortest path. But how does that help me find what the shortest path is?
If this isn’t a good problem, you can pick any other you like. Just don’t show me the answer for the Max Cut problem, because that’s the one I’m trying to work out and I want to get it on my own.
(The decision problem for this should be “Does there exist a cut of V such that the size of the cut is greater or equal to k”, correct?)
Now pick an edge in your distance graph and remove it (or give it a large enough cost that you’re sure the shortest path can’t include it). Does a path of the same length still exist for this new problem? If so, the path didn’t include that edge; if not, it did. Repeat.
Bit of a nitpick here. I don’t believe that the shortest path is necessarily unique, so all you can say is that is removed edge wasn’t part of at least one of the solutions. Of course, that doesn’t affect the correctness of your algorithm, as we’re looking for an optimal solution, not any particular one.
Thanks for your help. The light came on for me as soon as I read your post. I guess that this is the kind of thing that’s so obvious in retrospect that someone who’s been working in the area for a while wouldn’t even think that explaining how to do this would be necessary.