1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I'm sorry, but I cannot understand the question. What is maximum cardinality discrepancy? Maybe an example would help. $\endgroup$ – domotorp Nov 11 '17 at 19:30
  • $\begingroup$ @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). $\endgroup$ – Mohammad Al-Turkistany Nov 11 '17 at 19:40
  • $\begingroup$ What guarantees the existence of another solution? Why do you need that we are already given a solution? $\endgroup$ – domotorp Nov 11 '17 at 19:41
  • $\begingroup$ @domotorp Not aware of any guarantees. I need it to support my conjecture that no pesudo polynomial time Algorithms exist for finding another solution. $\endgroup$ – Mohammad Al-Turkistany Nov 11 '17 at 20:01
  • $\begingroup$ @domotorp I posted an example as your requested. $\endgroup$ – Mohammad Al-Turkistany Nov 11 '17 at 20:51
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do you guarantee that $||p_1|-|p_2||$ is maximum? Or you prove that finding any second solution (not optimal) is NP-hard? $\endgroup$ – Mohammad Al-Turkistany Nov 11 '17 at 21:13
  • $\begingroup$ Also, Why are you using a bunch of zeros in $p_1$? Typically, elements of partition problem are positive non-zero integers? $\endgroup$ – Mohammad Al-Turkistany Nov 11 '17 at 21:22
  • $\begingroup$ 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. $\endgroup$ – domotorp Nov 11 '17 at 21:23
  • $\begingroup$ What is N? Is it the sum of all elements? $\endgroup$ – Mohammad Al-Turkistany Nov 11 '17 at 21:26
  • 1
    $\begingroup$ It might be useful to mention this in the problem description. $\endgroup$ – domotorp Nov 11 '17 at 21:52

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.