# Is the ABC-partition problem NP-hard?

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?

• I don't know of a reduction from 3-partition to ABC-partition. But ABC-partition is straightforwardly a special case of 3-dimensional matching (en.wikipedia.org/wiki/3-dimensional_matching), and I think that would make a better source problem to attempt a reduction from. Commented Sep 10, 2020 at 22:24
• Show that ABC-partition is NP-hard by reduction from any NP-hard problem, then use the Cook–Levin theorem to obtain a reduction from 3-partition to ABC-partition. Commented Oct 25, 2020 at 8:04
• @YuvalFilmus these problems seem so similar, that I thought there may be a more direct reduction. Commented Oct 25, 2020 at 8:54
• Is there any particular reason you're interested in such a reduction? Commented Oct 25, 2020 at 9:57
• @YuvalFilmus My personal interest is mainly theoretic and educational. But there may be a practical application for approximation algorithms: if you have an approximation algorithm for one problem, then you can use the reduction to get an approximation algorithm for the other. I think it does not follow directly from the fact that both are NP-hard. Commented Oct 26, 2020 at 18:03