26

This question is related to an answer I posted in response to another question.

The 3-partition problem is the following problem:
Instance: Positive integers a1, …, an, where n=3m and the sum of the n integers is equal to mB, such that each ai satisfies B/4 < ai < B/2.
Question: Can the integers a1, …, an be partitioned into m multisets so that the sum of each multiset is equal to B?

It is well-known that the 3-partition problem is NP-complete in the strong sense that it remains NP-complete even if the numbers in the input are given in unary. See Garey and Johnson for a proof.

Questions: Does the 3-partition problem remain NP-complete if the numbers a1, …, an are all distinct? Does it remain NP-complete in the strong sense?

(My feeling is that the answers to both questions are probably yes because I do not see any reason why the problem should become easier if all numbers are distinct.)

It does not seem that the proof in Garey and Johnson establishes the NP-completeness of this restricted version.

In the answer to the other question linked above, I gave a proof that the 6-partition problem (defined analogously) with distinct numbers is NP-complete in the strong sense.

Community
  • 1
Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
  • 2
    I think this is an important problem; I found several papers in the literature that state or assume that the set version is hard, with no better justification than a citation to the multiset version in Garey and Johnson, and that use that assumption in a claim of NP-completeness for some other problem. – David Eppstein Aug 29 '10 at 19:18

1 Answers1

22

It is proved in [1, Corollary 7], that 3-partition is strongly NP-hard when the integers $a_1, \ldots, a_n$ are all distinct. The bounds $B/4 < a_i < B/2$ are not imposed in [1], but this should not make a difference.

[1]: Heather Hulett, Todd G. Will, Gerhard J. Woeginger: Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. Oper. Res. Lett. 36(5): 594-596 (2008). DOI

Serge Gaspers
  • 5,116
  • 29
  • 42
  • 6
    Imposing the bounds $B/4 < a_i < B/2$ is easily done by adding the same large number to all of the $a_i$. – David Eppstein Aug 30 '10 at 01:14
  • 1
    Indeed, it is straightforward to also impose these bounds. – Serge Gaspers Aug 30 '10 at 02:37
  • 2
    Thanks, it answers my question completely. Note that the partial Latin square completion problem can be easily formulated as a special case of the 3-dimensional matching. It did not occur to me to replace 3DM by PLSC, but after seeing the proof, the approach seems quite natural. – Tsuyoshi Ito Aug 30 '10 at 12:31