2
$\begingroup$

Let PARTITION-INTO-THREE-SETS be defined as following:

Input: Positive integers $a_1, ..., a_n$

Problem: Are there three pairwise disjoint sets $I, J, K \subseteq \{1, ..., n\}$ with $I \cup J \cup K = \{1, ..., n\}$, so that $\sum_{i \in I}{a_i} = \sum_{j \in J}{a_j} = \sum_{k \in K}{a_k}$?

It's easy to show, that PARTITION-INTO-THREE-SETS is NP-complete by doing a polynomial-time reduction PARTITION $\le$ PARTITION-INTO-THREE-SETS.

As PARTITION can be solved in pseudo-polynomial time with dynamic programming, there should be a way to solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time. Is there any solution to adapt the pseudo-polynomial algorithm for this problem?

$\endgroup$
2
$\begingroup$

Yes, there is a pseudo-polynomial algorithm for this problem.


Here is a wrong algorithm. Can you spot the biggest error?

Let $K=\sum_{i=1}^n{a_i}$. If $K$ is not divisible by 3, return none.

Run the pseudo-polynomial algorithm with $\lfloor K/2\rfloor$ replaced by $K/3$ everywhere. Adapting the algorithm so that it tracks the set of numbers whose sum is a given number. If that run of that algorithm return false, return none. If yes, remove the set of numbers from $a_1, a_2, \cdots, a_n$, we reduce the problem to find a subset of the remaining numbers whose sum is $K/3$, or half of the sum of remaining numbers, which is, of course, the partition problem again and which can be solved in pseudo-polynomial time.


Let us see how to construct a correct algorithm.

In the pseudo-polynomial algorithm for partition into two disjoint subsets, the goal is to compute function $p$ such that $p(i, j)$ is True if a subset of $\{x_1, \cdots, x_j \}$ sums to $i$ and False otherwise.

Now for partition into three disjoint subsets we have two variable parts, the first subset and the second subset (the third subset is the remaining integers), our goal is to compute function $q$ such that $q(h,i,j)$ is True if there are two disjoint subsets of $\{x_1, \cdots, x_j \}$ such that one of them has sum $h$ and the other has sum $i$, where $0\le h\le K/3, 0\le i\le K/3$. We have the following recurrence relation, ignoring a few corner cases because of the out-of-bound situations that are easy to figure out.

$q(h, i, j)$ is True if either of the following is true.

  • $q(h, i, j − 1)$
  • $q(h, i − x_j, j − 1)$
  • $q(h-x_j, i, j − 1)$

$q(h, i, j)$ is False otherwise.

I will leave the rest for readers to figure out.


Exercise 1. Write the correct algorithm roughly or fully in pseudocode or in your favorite programming language. Adapt it so that it will track the subsets in order to return the wanted three disjoint subsets.

Exercise 2. Show the time-complexity of the correct algorithm is $O(nK^2)$.

Exercise 3. Generalize to PARTITION-INTO-M-SETS for any given integer $M\ge2$.

$\endgroup$
  • $\begingroup$ I had the same idea too, but also realized, that it‘s not always working. $\endgroup$ – SmashTheStack Jan 24 at 22:48
  • $\begingroup$ Just let P to track the three parts at the same time. (Offline to take my meal.) $\endgroup$ – Apass.Jack Jan 24 at 22:51
  • $\begingroup$ This should work, but I‘m not quite shure how. Looking forward to your answer and already thanks a lot! $\endgroup$ – SmashTheStack Jan 24 at 22:56
  • $\begingroup$ That looks good. I will have closer look this afternoon. The error in the first solution is, that if we find a K/3 subset it is possible, that the remaining part cannot be partitioned although a partition into three sets exist. $\endgroup$ – SmashTheStack Jan 25 at 6:52
  • 1
    $\begingroup$ I have tested the algorithm and it worked after I figured out the corner cases! $\endgroup$ – SmashTheStack Jan 25 at 17:11

Your Answer

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

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