25
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Aug 29, 2010 at 19:18

1 Answer 1

Reset to default
21
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 6
    $\begingroup$ Imposing the bounds $B/4 < a_i < B/2$ is easily done by adding the same large number to all of the $a_i$. $\endgroup$
    – David Eppstein
    Aug 30, 2010 at 1:14
  • 1
    $\begingroup$ Indeed, it is straightforward to also impose these bounds. $\endgroup$
    – Serge Gaspers
    Aug 30, 2010 at 2:37
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Aug 30, 2010 at 12:31

Your Answer

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

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