3
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ Just out of curiosity, what's the source of this problem? $\endgroup$ – Mathguy May 31 '16 at 4:01
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ cool algorithm may I ask what if we had $c$ sets instead of $2$ your algorithm seems to scale like $nB^c$ correct? $\endgroup$ – user39969 May 31 '16 at 20:19
  • 1
    $\begingroup$ @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! $\endgroup$ – Mathguy Jun 1 '16 at 17:33
  • $\begingroup$ If $c$ is any where from $1$ to $n$ is the problem still $NP$ complete at each and every $c$? $\endgroup$ – Turbo Apr 30 '17 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy