Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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.) –  Raphael Mar 26 '12 at 6:57
    
What is meta-reduction? –  Mohammad Al-Turkistany Mar 26 '12 at 10:45
2  
I'm looking for Karp reduction of 3-Partition problem to Balanced Partition problem. I hope it is clear. –  Mohammad Al-Turkistany Mar 26 '12 at 11:43
1  
I'm happy with complex reductions. –  Mohammad Al-Turkistany Mar 26 '12 at 12:23
1  
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. –  Kaveh Apr 1 '12 at 1:51
show 2 more comments

2 Answers 2

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.

share|improve this answer
2  
It is hard to follow/believe your construction without elaborate ideas or the proof. Can you please provide at least one of both? –  Raphael Jul 4 '12 at 8:05
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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