14
$\begingroup$

The 3-Partition problem asks whether a set of $3n$ integers can be partitioned into $n$ sets of three integers such that each set sums up to some given integer $B$. The Balanced Partition problem asks whether $2n$ integers can be partitioned into two equal cardinality sets such that both sets have the same sum. Both problems are known to be NP-complete. However, 3-Partition is strongly NP-complete. I haven't seen in the literature any reduction from 3-Partition to Balanced Partition.

I'm looking for (simple) reduction from the 3-Partition to the Balanced Partition problem.

$\endgroup$
7
  • $\begingroup$ So you want a mapping from 3-Partition instances Balanced Partition instances? (the "meta-reduction" in the same direction would look for a mapping in the other.) $\endgroup$
    – Raphael
    Commented Mar 26, 2012 at 6:57
  • $\begingroup$ What is meta-reduction? $\endgroup$ Commented Mar 26, 2012 at 10:45
  • 2
    $\begingroup$ I'm looking for Karp reduction of 3-Partition problem to Balanced Partition problem. I hope it is clear. $\endgroup$ Commented Mar 26, 2012 at 11:43
  • 1
    $\begingroup$ I'm happy with complex reductions. $\endgroup$ Commented Mar 26, 2012 at 12:23
  • 2
    $\begingroup$ since it is weakly $\sf{NP\text{-}hard}$, you probably need a trick similar to the one about reducing 3SAT to it which will use numbers with lots of bits. See Sipser for example. And you can always combine multiple reduction to get what you want, see this. $\endgroup$
    – Kaveh
    Commented Apr 1, 2012 at 1:51

2 Answers 2

2
$\begingroup$

There are thousands of NP-complete problems in the literature, and most pairs do not have explicit reductions. Since polynomial-time many-one reductions compose, it suffices for researchers to stop when the graph of published reductions is strongly connected, making research into NP-completeness a much more scalable activity.

Although I really don't see the point, I'll humor you by giving a reasonably simple reduction from 3-PARTITION to BALANCED PARTITION, with a few hints about how the proof of correctness goes.

Let the input to the reduction be $x_1, \ldots, x_{3n}, B \in \mathbb Z$, an instance of 3-PARTITION. Verify that $\sum_{i\in[3n]} x_i = nB$. Let $\beta$ be a large number to be chosen later. For every $i \in [3n]$ and every $j \in [n]$, output two numbers $$x_i \beta^j + \beta^{n+j} + \beta^{2n+i} + \beta^{(i+4)n+j}\\ \beta^{(i+4)n+j}.$$ Intuitively, the first number means that $x_i$ is assigned to 3-partition $j$, and the second number means the opposite. The $x_i \beta^j$ term is used to track the sum of 3-partition $j$. The $\beta^{n+j}$ term is used to track the cardinality of 3-partition $j$. The $\beta^{2n+i}$ term is used to ensure that each $x_i$ is assigned exactly once. The $\beta^{(i+4)n+j}$ term is used to force these numbers into different balanced partitions.

Output two more numbers $$1 + \sum_{j\in[n]} \Bigl((n-2)B\beta^j + (3n-6)\beta^{n+j}\Bigr) + \sum_{i\in[3n]} (n-2)\beta^{2n+i}\\ 1.$$ The first number identifies its balanced partition as “true”, and the other, as “false”. The $1$ term is used to force these numbers into different balanced partitions. The other terms make up the difference between the sum of a 3-partition and the sum of its complement and the size of a 3-partition and the size of its complement and the number of times $x_i$ is assigned.

$\beta$ should be chosen large enough to ensure that “overflow” cannot occur.

$\endgroup$
1
  • 3
    $\begingroup$ It is hard to follow/believe your construction without elaborate ideas or the proof. Can you please provide at least one of both? $\endgroup$
    – Raphael
    Commented Jul 4, 2012 at 8:05
0
$\begingroup$

This paper, Fast Balanced Partitioning is Hard Even on Grids and Trees, by Andreas Emil Feldmann contains what you want! Good luck!

We will set up a general framework for a reduction from 3-PARTITION to different graph classes. This will be achieved by identifying some structural properties that a graph constructed from a 3-PARTITION instance has to fulfil, in order to show the hardness of the $k$-BALANCED PARTITIONING problem ...

$\endgroup$
1
  • 1
    $\begingroup$ This paper has nothing to do with the problem Mohammad asked. This one is about partitioning the vertices of a graph with respect to minimizing the number of edges between the partitions. $\endgroup$
    – domotorp
    Commented Dec 23, 2014 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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