Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 37:
== Proofs ==
Garey and Johnson (1975) originally proved 3-Partition to be NP-complete, by a reduction from [[3-dimensional matching]].<ref>[[Michael Garey|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.</ref> The classic reference by Garey and Johnson (1979) describes an NP-completeness proof, reducing from 3-dimensional matching to 4-partition to 3-partition.<ref>{{cite journal|author=[[Michael Garey|Garey, Michael R.]] and [[David S. Johnson]]|year=1975|title=Complexity results for multiprocessor scheduling under resource constraints|journal=SIAM Journal on Computing|volume=4|issue=4|pages=397–411|doi=10.1137/0204035}}</ref>
=== 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 ===
| |||