Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 34:
* The ABC-partition problem is also called '''[[Numerical 3-dimensional matching|numerical 3-d matching]]''', as it can also be reduced to the [[3-dimensional matching]] problem: given an instance of ABC-partition, construct a tripartite hypergraph with sides {{tmath|A, B, C}}, where there is an hyperedge {{tmath|(a, b, c)}} for every three vertices in {{tmath|A, B, C}} such that <math>a+b+c = T</math>. A matching in this hypergraph corresponds to a solution to ABC-partition.
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 ==
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> Logically, the reduction can be partitioned into several steps.
=== Reduction from 3d-matching to ABCD-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 of ABCD-partition as follows (where r := 32q):
* For each triplet t = {w<sub>i</sub>,x<sub>j</sub>,y<sub>k</sub>} in E, the set A contains an element u<sub>t</sub> = 10r<sup>4</sup>-kr<sup>3</sup>-jr<sup>2</sup>-ir.
* For each triplet t = {w<sub>i</sub>,x<sub>j</sub>,y<sub>k</sub>} in E, the set B contains w<sub>it</sub>, C contains x<sub>jt</sub>, and D contains 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 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:
** w<sub>i</sub>[1] = 10r<sup>4</sup>+ir; w<sub>i</sub>[2+] = 11r<sup>4</sup>+ir.
** x<sub>j</sub>[1] = 10r<sup>4</sup>+jr<sup>2</sup>; x<sub>j</sub>[2+] = 11r<sup>4</sup>+jr<sup>2</sup>.
** y<sub>k</sub>[1] = 10r<sup>4</sup>+kr<sup>3</sup>; y<sub>k</sub>[2+] = 8r<sup>4</sup>+kr<sup>3</sup>.
* 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>; and of the triplet element is added, the sum is 40r<sup>4</sup>.
* The threshold for the ABCD-partition instance is T=40r<sup>4</sup>. 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='' {''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 corresponding dummy elements.
In both cases, the sum of the 4-set is 40r<sup>4</sup> as needed.
Given a partition of ABCD, the sum of each 4-set is 40r<sup>4</sup>. Therefore, 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>; 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 ===
Given an instance of ABCD-partition with ''m'' elements per set, threshold ''T'', and sum ''mT'', we construct an instance of 4-partition with 4''m'' 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.
=== Reduction from 3d-matching to 4-partition ===
| |||