<p>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.</p>

<p>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$.</p>

<p>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$.</p>

<p>We can define a recurrence:</p>

<ul>
<li>$p(s, 0, 0)$ is true iff $s = 0$.</li>
<li>$p(s, i, c)$ is true if either $p(s, i-1, c)$ or $p(s - x_i, i-1, c-1)$ is true.</li>
<li>$p(s, i, c)$ is false otherwise.</li>
</ul>

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

<p>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$.</p>

<p>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:</p>

<pre><code>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
</code></pre>

<p>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$.</p>

CC BY-SA 3.0
2017-11-11T22:48:48.367Z
2017-11-11T22:48:48.367Z
Mikhail Rudoy
<p>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.</p>

CC BY-SA 3.0
2017-11-11T21:13:51.547Z
How do you guarantee that $||p_1|-|p_2||$ is maximum? Or you prove that finding any second solution (not optimal) is NP-hard?
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-11-11T21:22:22.747Z
Also, Why are you using a bunch of zeros in $p_1$? Typically, elements of partition problem are positive non-zero integers?
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-11-11T21:23:54.840Z
I'm proving that any second solution is $NP$-hard. The zeros won't make a difference, you can replace them with small numbers, like $1/N$, then they need to be evenly balanced if all other numbers are integers.
domotorp
CC BY-SA 3.0
2017-11-11T21:26:54.407Z
What is N? Is it the sum of all elements?
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-11-11T21:40:14.270Z
It seems that your proof proves weak NP-hardness of finding a second non-optimal solution. My interest is in proving strong NP-hardness for the version with optimality condition($||p_1|-|p_2|| $ is maximum).
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-11-11T21:52:55.273Z
It might be useful to mention this in the problem description.
domotorp
CC BY-SA 3.0
2017-11-11T21:54:44.063Z
Aha, I guessed that the motivation part was enough :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-11-11T21:06:41.983Z
2017-11-11T21:06:41.983Z
domotorp
<p>Motivated by this post, <a href="https://cstheory.stackexchange.com/questions/39437/strongly-np-complete-variants-of-subset-sum-or-partition-problem">Strongly NP-complete variants of subset sum or partition problem</a>, I am interested in this variant of partition:</p>

<p>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).</p>

<blockquote>
  <p>Is there an efficient algorithm to find such unbalanced partition or is it NP-hard?</p>
</blockquote>

<p>I am interested in pseudo-polynomial time algorithms or proving the problem to be <em>strongly</em> NP-hard.</p>

<p>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).</p>

CC BY-SA 3.0
2017-11-11T19:30:22.753Z
I'm sorry, but I cannot understand the question. What is maximum cardinality discrepancy? Maybe an example would help.
domotorp
CC BY-SA 3.0
2017-11-11T19:40:05.840Z
@domotorp we want a partition different from the given one such that the difference between the number of elements in the two parts is maximized (still both parts have the same sum).
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-11-11T19:41:18.437Z
What guarantees the existence of another solution? Why do you need that we are already given a solution?
domotorp
CC BY-SA 3.0
2017-11-11T20:01:56.723Z
@domotorp Not aware of any guarantees. I need it to support my conjecture that no pesudo polynomial time Algorithms exist for finding another solution.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-11-11T20:51:01.370Z
@domotorp I posted an example as your requested.
Mohammad Al-Turkistany
<cc.complexity-theory><np><partition-problem>
Complexity of a variant of partition problem
Mohammad Al-Turkistany
# Complexity of a variant of partition problem

(Asked by: username_0 on 2017-11-11)

Motivated by this post, [Strongly NP-complete variants of subset sum or partition problem](https://cstheory.stackexchange.com/questions/39437/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 @username_1) $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).

**Tags:** cc.complexity-theory, np, partition-problem

> **Comments:**
> **username_1**: I'm sorry, but I cannot understand the question. What is maximum cardinality discrepancy? Maybe an example would help.  
> **username_0**: @username_1 we want a partition different from the given one such that the difference between the number of elements in the two parts is maximized (still both parts have the same sum).  
> **username_1**: What guarantees the existence of another solution? Why do you need that we are already given a solution?  
> **username_0**: @username_1 Not aware of any guarantees. I need it to support my conjecture that no pesudo polynomial time Algorithms exist for finding another solution.  
> **username_0**: @username_1 I posted an example as your requested.  

---

## 2 answers

### Answer by username_2 on 2017-11-11. Score: 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 by username_1 on 2017-11-11. Score: 0

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.

> **Comments:**
> **username_0**: How do you guarantee that $||p_1|-|p_2||$ is maximum? Or you prove that finding any second solution (not optimal) is NP-hard?  
> **username_0**: Also, Why are you using a bunch of zeros in $p_1$? Typically, elements of partition problem are positive non-zero integers?  
> **username_1**: I'm proving that any second solution is $NP$-hard. The zeros won't make a difference, you can replace them with small numbers, like $1/N$, then they need to be evenly balanced if all other numbers are integers.  
> **username_0**: What is N? Is it the sum of all elements?  
> **username_0**: It seems that your proof proves weak NP-hardness of finding a second non-optimal solution. My interest is in proving strong NP-hardness for the version with optimality condition($||p_1|-|p_2|| $ is maximum).  
> **username_1**: It might be useful to mention this in the problem description.  
> **username_0**: Aha, I guessed that the motivation part was enough :)  

---

