SP15 is 3-Parttion.

The next problem is one of G&J’s “unpublished results” problems. I tried figuring out an elegant way to doing it, but couldn’t make it happen.

**The problem: **Numerical 3-Dimensional Matching. This is problem SP16 in the appendix.

**The description: ** Given three sets W, X, and Y, each containing the same amount (m) of elements with positive “sizes” and a positive bound B. Can we create m sets A_{1} through A_{m} (containing 3 elements each), such that:

- Each A
_{i}has exactly one element from W, X, and Y - The sum of the sizes of the elements in each A
_{i}is exactly B - Each element in W, X and Y is in some A
_{i}

**Example: **Suppose we have the following sets:

- W has elements with sizes {1,2,3,4}
- X has elements with sizes {12,11,7,5}
- Y has elements with sizes {1,1,4,5} (the ability to allow repeat numbers is why we define the sets as elements with sizes rather than sets of integers)

If B=14, then the partition where A_{1} is the first element in W, X, and Y, A_{2} is the second element in W, X, and Y, and so on gives each A_{i} set a sum of 14. Obviously, we don’t need to choose corresponding elements from W, X, and Y to form the sets (for example, rearranging the elements in X to be in increasing order doesn’t change whether the problem can be solved, just the exact composition of the A_{i} sets)

**Reduction: **I tried doing a reduction using 3-partition, but got stuck (I’ll show it below, in case you want to try to fix it). G&J refer you to Theorem 4.4 in the book, which is the proof that 3-partition itself is NP-Complete.

We can follow that along and do similar steps to our problem:

- Theorem 4.3 shows how to turn 3DM into 4-partition (a problem like 3-partition but each set in the solution has 4 elements instead of 3). Since the sets that are created in the 4-partition solution come from 4 different places (page 98 calls then a “u
_{i}, a w_{i}[·], an x_{j}[·], and a y_{k}[·]). Since these partitioned sets all add to the same total (B) and come from 4 disjoint parent sets, we can see how we could do basically the same reduction and show that the “numerical 4-dimensional matching problem” is NP-Complete. - Theorem 4,4 shows how to turn a 4-parition problem into a 3-partition problem. The idea is to add enough “pairing” and “filler” elements to the 3-partition instance to make any 4-partition set be split into two 3-partition sets, each consisting of 2 elements from the 4-parittion, plus the “pairing” element of one of the 2 elements chosen. We can do something similar converting numerical 4-dimensional matching to numerical 3-dimentional matching. (The difference is that we are given specifically which sets the elements are coming from) So, if we’re given W, X, Y, and Z in our numerical 4DM instance, we construct W’ to be elements from W and Y, X’ to be elements from X and Z, and Y’ to be the pairing elements of pairs from W’ and X’. We then need to add enough filler elements to our 3 sets in a similar way to the 3-partition proof (again, the difference is that we have to specifically assign them to W’, X’, or Y’. But that can be determined by how the 3-partition proof allocates the items)

**Difficulty: **If you have gone over the 3-partition reduction, this is probably a 6. Lots of tricky math but doable in a (hard) homework. But keep in mind you’re tacking it on to the difficulty 8 of understanding the 3-partition reduction in the first place.

**My reduction I couldn’t get to work: **I really want there to be an easier way to do this. I tried reducing from 3-partition directly because the problems are so similar. Here is where I got to:

We’re given a 3-parititon instance S, and an integer B. Our goal is to split S into sets of size 3 that all add up to B.

So, let’s use S to create 3 sets in our numerical 3DM instance:

- W has all of the elements in S
- X has all of the elements in S, but the sizes are each increased by 10B.
- Y has all of the elements in S, but the sizes are each increased by 100B.

This would make B’ be 111B.

S has a 3-parititon, then for each set {s_{i}, s_{j}, s_{k}}, we take the three sets {w_{i}, x_{j}, y_{k}}, {w_{j}, x_{k}, y_{i}}, and {w_{k}, x_{i}, y_{j}} This will solve the numerical 3DM instance.

My problem comes showing this in the other direction. If we have a numerical 3DM solution, we can only construct the 3-partition instance if the sets in the 3DM solution arrange themselves nicely like they do above. I need to show that if the 3DM solution has {w_{i}, x_{j}, y_{k}}, then the set in the 3DM solution that contains w_{j} also contains x_{i} (or x_{k}) and y_{k} (or y_{i}). I *think* you can get there by using the rules about how the bounds of the elements in the 3-partition instance work, but the work you need to do to show that it’s true makes this way of doing things no longer “easier” than the Theorem 4.4 proof I sketched above, so I gave up on it.

I still wish there was a more elegant way to transform this problem, though.