Complexity of a variant of partition problem

Question

Motivated by this post, Strongly NP-complete variants of subset sum or partition problem, I am interested in this variant of partition:

Given a solution to balanced partition problem (both parts have same cardinality), find another solution that have maximum cardinality discrepancy (i.e. $||P_1|-|P_2||$ is maximum).

Is there an efficient algorithm to find such unbalanced partition or is it NP-hard?

I am interested in pseudo-polynomial time algorithms or proving the problem to be strongly NP-hard.

P.S. Here is an example (as requested by @domotorp) $p1=\{2,2,3,4,5, 6\}$ and $p2= \{1, 1,3, 4, 5, 8\}$. The second solution is $p1=\{1,2,3,4,4, 8\}$ and $p2= \{ 1,2,3,5,5,6\}$ (the second solution is not optimal as p1 and p2 have equal number of elements).

Answer 1

The problem of finding a maximum cardinality discrepancy partition (or determining that one doesn't exist) is solvable in pseudo-polynomial time even if a balanced partition is not given.

Suppose that the input is a multiset of positive integers $S = \{x_1, \ldots, x_N\}$. Let $K = \sum_{i = 1}^Nx_i$. Below I demonstrate a dynamic programming algorithm for finding a maximum cardinality discrepancy partition of $S$.

Suppose $s$, $i$, and $c$ are variables with $0 \le s \le K$ and $0 \le c \le i \le N$. Then define $p(s, i, c)$ to be true if and only if there exists a multiset $T \subseteq \{x_1, \ldots, x_i\}$ whose cardinality is $c$ and whose sum is $s$.

We can define a recurrence:

• $p(s, 0, 0)$ is true iff $s = 0$.
• $p(s, i, c)$ is true if either $p(s, i-1, c)$ or $p(s - x_i, i-1, c-1)$ is true.
• $p(s, i, c)$ is false otherwise.

Using this recurrence we can compute the value of $p$ on all valid $s$, $i$, and $c$ in time polynomial in $N$ and $K$.

Furthermore, the predicate $\phi(c) = p(\frac{K}{2}, N, c)$ can be interpreted as "does there exist a subset of $S$ of cardinality $c$ whose sum is half of the sum of $S$?" or equivalently as "does there exist a partition of $S$ with cardinality discrepancy $|N-2c|$?". Thus, after finding all the values of $p$, we can simply look through all the values of $\phi(c) = p(\frac{K}{2}, N, c)$ and select the value of $c$ with $\phi(c)$ true for which the cardinality discrepancy $|N-2c|$ is largest. Call this value $c_0$. If $\phi(c)$ is never true then there is no partition of $S$.

All that's left is to actually find the partition of $S$ one of whose sets has size $c_0$. Here's an algorithm for doing this:

initialize P_1 and P_2 to be empty lists
initialize (s, c) to (k/2, c_0)
for i = N, N-1, ..., 1
| if p(s, i-1, c) is true:
| | add x_i to P_1
| else:
| | add x_i to P_2
| | set (s, c) to (s - x_i, c-1)
output P_1 and P_2

Notice that this algorithm is just following the recurrence of $p$ back from $p(\frac{K}{2}, N, c_0)$ to $p(0,0,0)$. That is, the algorithm maintains the invariant that $p(s, i, c)$ is always true at the start of the loop (this is easy to prove by induction). The invariant even continues to hold after the last iteration of the loop; that is, $p(s, 0, c)$ is true after the loop. Since $p(s, 0, c)$ is only true if $s = c = 0$, we can deduce that $s$ and $c$ decrease from $\frac{K}{2}$ and $c_0$ to $0$ over the course of a loop. Looking at the only line where $s$ and $c$ change, this clearly implies that list $P_2$ ends up containing exactly $c_0$ elements whose total sum is $\frac{K}{2}$. In other words, $P_1$ and $P_2$ form a partition of $S$ whose cardinality discrepancy is $|N - 2c_0|$, which by definition of $c_0$ is exactly the largest possible cardinality discrepancy for any partition of $S$.

Answer 2

Let the first part of your given solution be $p_1=\{N,N,0,\ldots,0\}$. Then in any other solution these two elements of weight $N$ must be in different parts, therefore the problem reduces to finding a (not necessarily balanced) partition of the elements of $p_2$, which is $NP$-hard.