HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the ABC-partition problem NP-hard?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemthepartitionhardabc

Problem

In the ABC-partition problem, there are three sets $A, B, C$ with $m$ positive integers in each. The sum of all integers is $m T$. The goal is to construct $m$ triplets with the same sum $T$, each of which contains exactly one integer from $A, B$ and $C$.

The problem "feels" NP-hard, but I could not find a proof for this. I could only find reductions in the wrong direction:

  • Reduction from ABC-partition to 3-partition is easy: replace each $a \in A$ with $8a+1$, each $b \in B$ with $8b+2$, and each $c \in C$ with $8c+4$. This forces the 3-partition oracle to construct with exactly one item from each of $A$, $B$ and $C$.



  • Reduction from ABC-partition to 3-dimensional matching is easy too: keep the items in $A, B, C$ as they are, and add a hyperedge $\{a,b,c\}$ iff $a+b+c = T$.



  • I also found a reduction from 3-dimensional matching to ABCD-partition, which is similar to ABC-partition but with four sets; and a reduction from 4-partition to 3-partition.



But, none of these reductions shows that ABC-partition is NP hard.

Previously I asked specifically about a reduction from 3-partition from ABC-partition; now I am not even sure if it is NP-hard. Is it?

Solution

This seems to be the Numerical 3D matching problem. Wikipedia cites a proof of NP-Hardness by Garey and Johnson (problem SP16).

Context

StackExchange Computer Science Q#129999, answer score: 2

Revisions (0)

No revisions yet.