7
$\begingroup$

I'm looking for research into this problem -- computational complexity, solution algorithms, approximation algorithms, etc. If it has a canonical name, that would help me look into prior research.

Suppose there are two sets of integers S1 and S2 that are subsets of the positive integers.

The sum of all numbers in S1 equals the sum of all numbers in S2.

Find all subsets of S1 and subsets of S2 such that the the subsets sum up equivalently between the two. For example:

S1 = (1,2,3,4) S2 = (2, 2, 3, 3)

solutions:

(1+2 = 3, 3 = 3, 4 = 2+2)
(1+2+3 = 3+3, 4 = 2+2)
(1+2+3+4 = 2+2+3+3)
(1+3 = 2+2, 2+4 = 3+3)
(1+3+4 = 2+3+3, 2=2)
(2+3 = 2+3, 1+4 = 2+3)
etc.

You could also frame this in terms of making all numbers in S2 negative, collapsing them into one set, and finding all permutation subsets such that each subset adds up to 0.

If the numbers in S2 are expressed as negative numbers, the problem could also be expressed as a graph in which each node is an integer, and the goal is to find all possible disjoint sets such that the members of each set add up to 0.

$\endgroup$
  • $\begingroup$ Instead of listing all such partition pairs explicitly, it could also be interesting to list just the finest ones (in your example, these are (1+2=3,3=3,4=2+2),(1+3=2+2,2+4=3+3),(1+4=2+3,2=2,3=3)). These still uniquely determine the set of solutions. $\endgroup$ – Klaus Draeger Jun 28 '15 at 23:38
2
$\begingroup$

I've never heard of this problem before, but it's clearly NP-hard.

There's a simple polynomial time reduction from subset-sum to this problem. All you have to do is take an instance of subset-sum such as: {x1, x2, x3, ... , x_n} ...and map it to this instance of the problem you describe: S1 = {x1, x2, x3, ..., x_n}; S2 = {0}.

(I initially misread your question and thought that you were talking about a decision problem; since that was not what you meant, I cannot say anything beyond whether or not it is NP-hard except that it is EXPTIME. It is likely not NP; see the comments below.)

Either way, I don't think you are going to find any good solution or approximation algorithms.

$\endgroup$
  • 3
    $\begingroup$ The question asks for all such subsets, so I don't think it belongs to NP. $\endgroup$ – Austin Buchanan Jun 28 '15 at 19:17
  • $\begingroup$ Yes, as Austin points out it's not even a decision problem. It could take exponential time just to enumerate all such subsets (for example, if $S_1 = S_2 = \{1, \ldots, n\}$). $\endgroup$ – Huck Bennett Jun 28 '15 at 19:22
  • $\begingroup$ Oops...didn't read carefully enough. I'll edit in a moment. $\endgroup$ – Philip White Jun 28 '15 at 21:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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