Disjoint Subset Sum Reduction (NP-Complete)

Question

I am using past materials to review for an upcoming assignment and came across this question:

Disjoint Subset Sum:

Input: A set of integers S and a goal g(in the set of natural numbers)

Output: YES if there are at least two disjoint(non-overlapping) subsets of S where the elements of each subset sum to exactly to g otherwise NO

I need to prove that this is NP-Complete.

I know how to prove it is in NP. However, I am struggling with the reduction from subset sum to this problem. My initial thought was adding 0 and g to the set in subset sum to modify the input because if subsetsum had a subset that summed to g then the second disjoint subset must be 0 and g. The problem with this is that subset sum takes in a set of non-negative integers(according to the way I learned it) so 0 and g can already be in the set. I have tried other ways but I can't seem to account for any edge case that arises.

I think there is an edge case: adding 'g' to some subset S doesn't change if g already exists(so I think the reduction has to do with adding g)

Any help is appreciated! I wasn't able to find anything similar online(only the partition problem) so I'm asking here!

Answer 1

You are almost there. First of all it is useless to add $0$, even if it were allowed by the problem statement. Second, if the subset-sum instance is trivially a yes-instance because its set of integers already contains the target value (notice that you can detect this in polynomial time) then you can return any fixed yes-instance of disjoint subset-sum.

To summarize, if $\langle S', g' \rangle$ is an instance of subset-sum, a possible polynomial-time reduction to disjoint subset-sum returns the instance $\langle S,g\rangle$ where:

• If $g' \in S'$ then $S =\{1, 2, 3\}$ and $g = 3$;
• Otherwise ($g' \not \in S'$), $S = S' \cup \{g'\}$ and $g = g'$.

To see that this works, consider a yes-instance $\langle S', g' \rangle$ of subset-sum. If $g' \in S'$ then $\langle S,g\rangle$ is trivially a yes instance of disjoint subset-sum. If $g' \not \in S'$, then let $S^* \subseteq S^*$ be a set such that $\sum_{s \in S^*} s = g'$. A solution to the disjoint subset-sum problem is given by the two sets $S^*$ and $\{g'\}$.

Suppose now that $\langle S,g\rangle$ is a yes-instance of disjoint subset-sum. Then there are two disjoint sets $S_1, S_2 \subseteq S$ such that $\sum_{s \in S_1} s = \sum_{s \in S_2} s = g = g'$. Since at least one of $S_1$ and $S_2$ does not contain $g'$, this set is also a solution to the original subset-sum instance $\langle S', g' \rangle$.