Common subset sum fast algorithm

Question

Suppose of I two sets of $n$ integers bounded in $[-B,B]$. The integers are $$a_1,\dots,a_n$$ $$b_1,\dots,b_n$$

I want to find if there is a common subset $I\subseteq\{1,\dots,n\}$ such that $$\sum_{i\in I}a_i=0$$$$\sum_{i\in I}b_i=0$$

This problem is $NP$-complete.

Is there a pseudo polynomial time algorithm with complexity for this problem like the regular subset sum problem on bounded integers which has an $O(B^2)$ algorithm (https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution)?

• Mathguy: Just out of curiosity, what's the source of this problem?

Answer 1

Yes, we shall use dynamic programming and extend our subset-sum algorithm here.

• Let $R(i, \ s, \ t)$ be true iff there exists a subset $K \in \{1, ... i\}$ such that $$\sum_{i \in K} a_i = s \quad and \quad\sum_{i \in K} b_i = t.$$

Which subproblem would then give us the result we need? $R(n, 0, 0)$!

Now, let's find a recursive relation for our subproblem in terms of smaller subproblems: $$R(i, \ s, \ t) := [(a_i==s) \wedge (b_i==t)] \\\vee R(i-1, \ s, \ t)\\\vee\ R(i-1, \ s-a_i, \ t-b_i) $$

where, $\vee$ is the OR operator and $\wedge$ is the AND operator.

This relation works on the inclusion-exclusion principle - either we include the $i$th index in our subset $K$ or not. But the caveat here is that if we include the $i$th index, we must include both $a_i$ and $b_i$.

• If we do not include the $i$th index, $R(i, \ s, \ t)$ reduces simply to $R(i-1, \ s, \ t).$
• If we do include the $i$th index, either ($a_i$ should be $s$) AND ($b_i$ should be t). Or, we must have some common subset of the two sets summing to $s-a_i$ and $t-b_i$ respectively i.e. $R(i-1, \ s-a_i, \ t-b_i)$ should be true.

For the sake of completeness, the base cases are $R(1, \ s, \ t) := (a_1 ==s) \wedge (b_1==t)$.

Edit:The runtime of the algorithm then is $O(n^3{B^2})$ (Why?), which is pseudo-polynomial too.

• user39969: cool algorithm may I ask what if we had $c$ sets instead of 2ドル$ your algorithm seems to scale like $nB^c$ correct?
• Mathguy: @Student. Nope, it would be$O({n^{(c+1)}} \ {B^c})$ (can you see why?). You would have your subproblem definition as $R(i,s1,s2...sc). $ And if you found my answer correct, could you accept (the green tick) the answer? :) A higher rep always helps, haha!
• Turbo: If $c$ is any where from 1ドル$ to $n$ is the problem still $NP$ complete at each and every $c$?