Numerical 3-dimensional matching

Numerical 3-dimensional matching is an NP-complete decision problem. It is given by three multisets of integers $X$, $Y$ and $Z$, each containing $k$ elements, and a bound $b$. The goal is to select a subset $M$ of $X\times Y\times Z$ such that every integer in $X$, $Y$ and $Z$ occurs exactly once and that for every triple $(x,y,z)$ in the subset $x+y+z=b$ holds. This problem is labeled as [SP16] in.

Example

Take $X=\{3,4,4\}$, $Y=\{1,4,6\}$ and $Z=\{1,2,5\}$, and $b=10$. This instance has a solution, namely $\{(3,6,1),(4,4,2),(4,1,5)\}$. Note that each triple sums to $b=10$. The set $\{(3,6,1),(3,4,2),(4,1,5)\}$ is not a solution for several reasons: not every number is used (a $4\in X$ is missing), a number is used too often (the $3\in X$) and not every triple sums to $b$ (since $3+4+2=9\neq b=10$). However, there is at least one solution to this problem, which is the property we are interested in with decision problems. If we would take $b=11$ for the same $X$, $Y$ and $Z$, this problem would have no solution (all numbers sum to $30$, which is not equal to $k\cdot b=33$ in this case).

Related problems

Every instance of the Numerical 3-dimensional matching problem is an instance of both the 3-partition problem, and the 3-dimensional matching problem.

Given an instance of numeric 3d-matching , construct a tripartite hypergraph with sides $X$, $Y$ and $Z$, where there is an hyperedge $(x,y,z)$ if and only if $x+y+z=T$. A matching in this hypergraph corresponds to a solution to ABC-partition.

Proof of NP-completeness

The numerical 3-d matching problem is problem [SP16] of Garey and Johnson. They claim it is NP-complete, and refer to, but the claim is not proved at that source. The NP-hardness of the related problem 3-partition is done in by a reduction from 3-dimensional matching via 4-partition. To prove NP-completeness of the numerical 3-dimensional matching, the proof should be similar, but a reduction from 3-dimensional matching via the numerical 4-dimensional matching problem should be used. Explicit proofs of NP-hardness are given in later papers:

• Yu, Hoogeveen and Lenstra prove NP-hardness of a very restricted version of Numerical 3-Dimensional Matching, in which two of the three sets contain only the numbers 1,...,k.
• Caracciolo, Fichera, and Sportiello prove NP-hardness of Numerical 3-Dimensional Matching and related problems by reduction from NAE-SAT. The reduction is linear, that is, the size of the reduced instance is a linear function of the size of the original instance.