2
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

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

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