0
$\begingroup$

The "classical" partition problem asks whether a given multiset $S$ of positive integers can be partitioned into two subsets $S_1$ and $S_2$ such that the sum of the numbers in $S_1$ equals the sum of the numbers in $S_2$. The problem is known to be NP-hard.

I want to know if a similar problem is also NP-hard (I believe so, but can't proof it).

Given a set $S$ which consist of pairs of positiv integers (e.g. $S=\{\{2,7\},\{3,9\},\{4,5\},\{6,8\}\}$). Can $S$ be partitioned into two subsets $S_1$ and $S_2$ such that the sum of the numbers in $S_1$ equals $S_2$ and no two numbers from $S_1$ belong to the same pair from $S$ (which means that if one number from a pair is choosen to be in $S_1$ the other one must be in $S_2$).

For example a valid solution to the set $S$ from above would be $S_1=\{2,9,5,6\}$ and $S_2=\{7,3,4,8\}$. Here each sum is equal to $22$ and from each pair of numbers from $S$ exactly one number can be found in $S_1$ (or equally in $S_2$).

$\endgroup$
2
  • 1
    $\begingroup$ Yes, this is still NP-complete. If you try hard enough, you will be able to show it. $\endgroup$ Jun 10, 2022 at 10:09
  • $\begingroup$ @YuvalFilmus I see that I could choose an instance where one element of each pair is $0$. This would leave me with the classical partition problem. Thus our problem must be at least as hard. Is there some other obvious reduction where we assume that each integer must be strictly greater than $0$? $\endgroup$ Jun 10, 2022 at 11:13

1 Answer 1

2
$\begingroup$

As you mentioned the first problem can be reduced to the second one by replacing each positive integer $a_i\in S$ by a paired $(a_i,0)$. Moreover, the second problem can be reduced to the first one by replacing each paired $(a_i,b_i)\in S$ by a pisitive integer $c_i=|a_i-b_i|$ and after partitioning (suppose that $a_i\ge b_i$), if $c_i$ is in $s_1$ then let $a_i\in s_1$ and $b_i\in s_2$.

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