3-partition problem

(Redirected from 3-partition)

The 3-partition problem is a strongly NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triplets that all have the same sum. More precisely:

  • Input: a multiset S containing n positive integer elements.
  • Conditions: S must be partitionable into m triplets, S1, S2, …, Sm, where n = 3m. These triplets partition S in the sense that they are disjoint and they cover S. The target value T is computed by taking the sum of all elements in S, then divided by m.
  • Output: whether or not there exists a partition of S such that, for all triplets, the sum of the elements in each triplet equals T.

The 3-partition problem remains strongly NP-complete under the restriction that every integer in S is strictly between T/4 and T/2.

Example

edit
  1. The set   can be partitioned into the four sets  , each of which sums to T = 90.
  2. The set   can be partitioned into the two sets   each of which sum to T = 15.
  3. (every integer in S is strictly between T/4 and T/2):  , thus m=2, and T=15. There is feasible 3-partition  .
  4. (every integer in S is strictly between T/4 and T/2):  , thus m=2, and T=15. There is no feasible solution.

Strong NP-completeness

edit

The 3-partition problem remains NP-complete even when the integers in S are bounded above by a polynomial in n. In other words, the problem remains NP-complete even when representing the numbers in the input instance in unary. i.e., 3-partition is NP-complete in the strong sense or strongly NP-complete. This property, and 3-partition in general, is useful in many reductions where numbers are naturally represented in unary.

3-Partition vs Partition

edit

The 3-partition problem is similar to the partition problem, in which the goal is to partition S into two subsets with equal sum, and the multiway number partitioning, in which the goal is to partition S into k subsets with equal sum, where k is a fixed parameter. In 3-Partition the goal is to partition S into m = n/3 subsets, not just a fixed number of subsets, with equal sum. Partition is "easier" than 3-Partition: while 3-Partition is strongly NP-hard, Partition is only weakly NP-hard - it is hard only when the numbers are encoded in non-unary system, and have value exponential in n. When the values are polynomial in n, Partition can be solved in polynomial time using the pseudopolynomial time number partitioning algorithm.

Variants

edit

In the unrestricted-input variant, the inputs can be arbitrary integers; in the restricted-input variant, the inputs must be in (T/4, T/2). The restricted version is as hard as the unrestricted version: given an instance Su of the unrestricted variant, construct a new instance of the restricted version Sr ≔ {s + 2 T  | s ∈ Su}. Every solution of Su corresponds to a solution of Sr but with a sum of 7 T  instead of T, and every element of Sr is in [2 T , 3 T ] which is contained in (T /4, 7 T /2).

In the distinct-input variant, the inputs must be in (T/4, T/2), and in addition, they must all be distinct integers. It, too, is as hard as the unrestricted version.[1]

In the unrestricted-output variant, the m output subsets can be of arbitrary size - not necessarily 3 (but they still need to have the same sum T). The restricted-output variant can be reduced to the unrestricted-variant: given an instance Sr of the restricted variant, with 3m items summing up to mT, construct a new instance of the unrestricted variant Su ≔ {s + 2T | s ∈ Sr}, with 3m items summing up to 7mT, and with target sum 7 T . Every solution of Sr naturally corresponds to a solution of Su. Conversely, in every solution of Su, since the target sum is 7 T  and each element is in (T /4, 7 T /2), there must be exactly 3 elements per set, so it corresponds to a solution of Sr.

The ABC-partition problem (also called numerical 3-d matching) is a variant in which, instead of a set S with 3 m  integers, there are three sets A, B, C with m integers in each. The sum of numbers in all sets is  . The goal is to construct m triplets, each of which contains one element from A, one from B and one from C, such that the sum of each triplet is T.[2]

The 4-partition problem is a variant in which S contains n = 4 m  integers, the sum of all integers is  , and the goal is to partition it into m quadruplets, all with a sum of T. It can be assumed that each integer is strictly between T/5 and T/3. Similarly, ABCD-parititon is a variant of 4-partition in which each there are 4 input sets and each quadruplet should contain one element from each set.

Proofs

edit

Garey and Johnson (1975) originally proved 3-Partition to be NP-complete, by a reduction from 3-dimensional matching.[3] The classic reference by Garey and Johnson (1979) describes an NP-completeness proof, reducing from 3-dimensional matching to 4-partition to 3-partition.[4] Logically, the reduction can be partitioned into several steps.

Reduction from 3d-matching to ABCD-partition

edit

We are given an instance of E of 3d-matching, containing some m triplets {wi,xj,yk}, where the vertices are w1,...,wq and x1,...,xq and y1,...,yq. We construct an instance of ABCD-partition with 4*m elements, as follows (where r := 32q):

  • For each triplet t = {wi,xj,yk} in E, the set A contains an element ut = 10r4-kr3-jr2-ir.
  • For each triplet t = {wi,xj,yk} in E, the set B contains wit, C contains xjt, and D contains ykt. So for each of wi, xj, yk, there may be many corresponding elements in B, C, D - one for each triplet in which they appear. We consider one of these elements (denoted by "1") as the "real" one, and the others as "dummy" ones. The element sizes are as follows:
    • wi[1] = 10r4+ir; wi[2..] = 11r4+ir.
    • xj[1] = 10r4+jr2; xj[2..] = 11r4+jr2.
    • yk[1] = 10r4+kr3; yk[2..] = 8r4+kr3.
  • The sum of every three "real" elements or every three "dummy" elements is 30r4+ir+jr2+kr3; and if the triplet element is added, the sum is 40r4.
  • The threshold for the ABCD-partition instance is T=40r4. Note that the size of each element is in (T/3,T/5).

Given a perfect matching in E, we construct a 4-partition of ABCD as follows:

  • For each triplet t= {wi,xj,yk} in the matching, we construct a 4-set {ut, wi[1], xj[1], yk[1]}.
  • For each triplet not in the matching, we construct a similar 4-set, but with the corresponding dummy elements.

In both cases, the sum of the 4-set is 40r4 as needed.

Given a partition of ABCD, the sum of each 4-set is 40r4. Therefore, the terms with r, r2 and r3 must cancel out, and the terms with r4 must sum up to 40r4; so the 4-set must contain a triplet and 3 matching "real" elements, or a triplet and 3 matching "dummy" elements. From the triplets with the 3 matching "real" elements, we construct a valid perfect matching in E.

Note that, in the above reduction, the size of each element is polynomial in the input size; hence, this reduction shows that ABCD-partition is strongly NP-hard.

Reduction from ABCD-partition to 4-partition

edit

Given an instance of ABCD-partition with m elements per set, threshold T, and sum mT, we construct an instance of 4-partition with 4m elements:

  • For each element a in A, the corresponding element has size 16a+1;
  • For each element b in B, the corresponding element has size 16b+2;
  • For each element c in C, the corresponding element has size 16c+4;
  • For each element d in D, the corresponding element has size 16d+8.

All in all, the sum is 16mT+15m, and the new threshold is 16T+15.

Every ABCD-partition corresponds naturally to a 4-partition. Conversely, in every 4-partition, the sum modulo 16 is 15, and therefore it must contain exactly one item with size modulo 16 = 1, 2, 4, 8; this corresponds to exactly one item from A, B, C, D, from which we can construct an ABCD-partition.

Using a similar reduction, ABC-partition can be reduced to 3-partition.

Reduction from 4-partition to 3-partition

edit

We are given an instance A of 4-partition: 4m integers, a1,...,a4m, each of which in the range (T/3,T/5), summing up to mT. We construct an instance B of 3-partition as follows:

  • For each ai in A, B contains a "regular" element wi = 4*(5T+ai)+1. All in all there are 4m regular elements, summing up to 81mT + 4m.
  • For each pair of elements ai,aj in A, B contains two "pairing" elements: uij = 4*(6T - ai - aj)+2 and uij' = 4*(5T + ai + aj)+2. All in all there are 4m*(4m-1) pairing elements, summing up to (88mT+16m)*(4m-1).
  • Additionally, B contains 8m2-3m "filler" elements, with size 20T, and total sum (8m2-3m)*20T.
  • All in all, B contains 24m2-3m = 3(8m2-m) elements, with sum (64T+4)*(8m2-m).
  • The threshold for the 3-partition instance is 64T+4; note that the sizes of all elements in B are in (16T+1,32T+2).

Given a 4-partition of A, we construct a 3-partition for B as follows:

  • For each 4-set {a1,a2,a3,a4} with sum T, we construct a 3-set {w1,w2,u12} with sum 4*(5T+a1+5T+a2+6T-a1-a2)+1+1+2=64T+4 and another 3-set {w3,w4,u12'} with sum 4*(5T+a3+5T+a4+5T+a1+a2)+1+1+2=64T+4. These sets contain all 4m regular elements and 2m matching pairs of pairing elements.
  • From the remaining elements, we construct 3-sets {uij,uij',filler} with sum 4*(6T-ai-aj+5T+ai+aj+5T)+2+2=64T+4.

Conversely, given a 3-partition of B, the sum of each 3-set is a multiple of 4, so it must contain either two regular items and one pairing item, or two pairing items and one filler item:

  • If a 3-set contains two pairing items uij, ukl and one filler item, then the sum of the two pairing items must be 44T+4 = 4*(5T+6T)+2+2, so they must have matching sizes (ai+aj=ak+al). Therefore, by replacing as needed, we can assume that the two pairing items are in fact uij and uij'. Therefore, the remaining pairing items also consist of n matching pairs.
  • Therefore, the remaining 3-sets can be partitioned into two groups: n 3-sets containing the items uij, and n 3-sets containing the items uij'. In each matching pair of 3-sets, the sum of the two pairing items uij+uij' is 44T+4, so the sum of the four regular items is 84T+4. Therefore, from the four regular items, we construct a 4-set in A, with sum T.

Applications

edit

The NP-hardness of 3-partition was used to prove the NP-hardness rectangle packing, as well as of Tetris[5][6] and some other puzzles,[7] and some job scheduling problems.[8]

References

edit
  1. ^ Hulett, Heather; Will, Todd G.; Woeginger, Gerhard J. (2008-09-01). "Multigraph realizations of degree sequences: Maximization is easy, minimization is hard". Operations Research Letters. 36 (5): 594–596. doi:10.1016/j.orl.2008.05.004. ISSN 0167-6377.
  2. ^ Demaine, Erik (2015). "MIT OpenCourseWare - Hardness made Easy 2 - 3-Partition I". Youtube. Archived from the original on 2021-12-14.
  3. ^ Garey, Michael R. and David S. Johnson (1975). "Complexity results for multiprocessor scheduling under resource constraints". SIAM Journal on Computing. 4 (4): 397–411. doi:10.1137/0204035.
  4. ^ Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5. Pages 96–105 and 224.
  5. ^ "Tetris is hard, even to approximate". Nature. 2002-10-28. doi:10.1038/news021021-9. ISSN 0028-0836.
  6. ^ BREUKELAAR, RON; DEMAINE, ERIK D.; HOHENBERGER, SUSAN; HOOGEBOOM, HENDRIK JAN; KOSTERS, WALTER A.; LIBEN-NOWELL, DAVID (2004-04-01). "Tetris is Hard, Even to Approximate". International Journal of Computational Geometry & Applications. 14 (1n02): 41–68. arXiv:cs/0210020. doi:10.1142/s0218195904001354. ISSN 0218-1959. S2CID 1177.
  7. ^ Demaine, Erik D.; Demaine, Martin L. (2007-06-01). "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity". Graphs and Combinatorics. 23 (S1): 195–208. doi:10.1007/s00373-007-0713-4. ISSN 0911-0119. S2CID 17190810.
  8. ^ Bernstein, D.; Rodeh, M.; Gertner, I. (1989). "On the complexity of scheduling problems for parallel/pipelined machines". IEEE Transactions on Computers. 38 (9): 1308–1313. doi:10.1109/12.29469. ISSN 0018-9340.