1
$\begingroup$

I'm a little lost and don't know how to approach this problem.

Show the partition search problem can be poly-time reduced to the partition decision problem, the partition decision problem takes an input set of numbers and returns true if there is a subset of the initial set that sums up to half the total sum of the initial set.

With problems like ham-path search, clique search and SAT search, the key was to build the solution one piece at a time using the results from the decision "oracle". But I need to know how to approach this problem.

Initially, I thought about removing elements from the set while verifying if there is a partition in the remaining set, which led me nowhere. Now I'm wondering if adding elements to the initial set would have any results. I noticed if the initial set has a partition, adding elements to the set would then only have a partition if the added element is even, but I don't see how this can generate a subset of the original set that satisfies partition search. Am I going off the wrong track? Any pointers would be appreciated.

$\endgroup$
1
$\begingroup$

The standard approach works fine to reduce the problem size. Given a "true" instance, $n$ elements which can be partitioned, you want to be able to reduce it to a smaller sized problem. Grab any 2 elements, and combine them into one (having their sum as its size), and now you have an instance with $n-1$ elements. If the answer to that instance is yes, great. If it is no? They must go into different partitions, which (effectively) adds their difference to whichever partition got the larger one. Get rid of both, but add the difference as a new element. In either case, you have $n-1$ elements in your new instance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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