|
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.
=== Reduction from 3d-matching to 4-partition ===
We are given an instance of E of 3d-matching, containing some ''m'' triplets {w<sub>i</sub>,x<sub>j</sub>,y<sub>k</sub>}, where the vertices are w<sub>1</sub>,...,w<sub>q</sub> and x<sub>1</sub>,...,x<sub>q</sub> and y<sub>1</sub>,...,y<sub>q</sub>. We construct an instance A of 4-partition as follows (where r := 32q):
* For each triplet t = {w<sub>i</sub>,x<sub>j</sub>,y<sub>k</sub>} in E, A contains an element u<sub>t</sub> = 10r<sup>4</sup>-kr<sup>3</sup>-jr<sup>2</sup>-ir+8.
* For each triplet t = {w<sub>i</sub>,x<sub>j</sub>,y<sub>k</sub>} in E, A contains elements w<sub>it</sub>, x<sub>jt</sub>, y<sub>kt</sub>. So for each of w<sub>i</sub>, x<sub>j</sub>, y<sub>k</sub>, there may be many corresponding elements in A - 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:
** w<sub>i</sub>[1] = 10r<sup>4</sup>+ir+1; w<sub>i</sub>[2+] = 11r<sup>4</sup>+ir+1.
** x<sub>j</sub>[1] = 10r<sup>4</sup>+jr<sup>2</sup>+2; x<sub>j</sub>[2+] = 11r<sup>4</sup>+jr<sup>2</sup>+2.
** y<sub>k</sub>[1] = 10r<sup>4</sup>+kr<sup>3</sup>+4; y<sub>k</sub>[2+] = 8r<sup>4</sup>+kr<sup>3</sup>+4.
* The sum of every three "real" elements or every three "dummy" elements is 30r<sup>4</sup>+ir+jr<sup>2</sup>+kr<sup>3</sup>+7; and of the triplet element is added, the sum is 40r<sup>4</sup>+15.
* The threshold for the 4-partition instance is T=40r<sup>4</sup>+15. 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 A as follows:
* For each triplet ''t='' {''w<sub>i</sub>,x<sub>j</sub>,y<sub>k</sub>''} in the matching, we construct a 4-set {u<sub>t</sub>, w<sub>i</sub>[1], x<sub>j</sub>[1], y<sub>k</sub>[1]}.
* For each triplet not in the matching, we construct a similar 4-set, but with the dummy elements.
In both cases, the sum of the 4-set is 40r<sup>4</sup>+15 as needed.
Given a 4-partition of A, the sum of each 4-set is 40r<sup>4</sup>+15, and therefore it must contain elements whose size ends with +1, +2, +4, +8; that is, three vertex-elements and one triplet-element. Moreover, the terms with r, r<sup>2</sup> and r<sup>3</sup> must cancel out, and the terms with r<sup>4</sup> must sum up to 40r<sup>4</sup>; therefore, 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 4-partition is ''strongly'' NP-hard.
=== Reduction from 4-partition to 3-partition ===
|
