Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 37:
=== 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 with 4*''m'' elements, 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
** x<sub>j</sub>[1] = 10r<sup>4</sup>+jr<sup>2</sup>; x<sub>j</sub>[2
** y<sub>k</sub>[1] = 10r<sup>4</sup>+kr<sup>3</sup>; y<sub>k</sub>[2
* 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 if 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).
| |||