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.^[1]

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).

Proof of NP-completeness

NP-completeness of the 3-partition problem is stated by Garey and Johnson in "Computers and Intractability; A Guide to the Theory of NP-Completeness".^[1] It is done by a reduction from 3-dimensional matching via 4-partition. To prove NP-completeness of the numerical 3-dimensional matching, the proof is similar, but a reduction from 3-dimensional matching via the numerical 4-dimensional matching problem should be used.

References

↑ 1.0 1.1 Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5

Numerical 3-dimensional matching

Example

Related problems

Proof of NP-completeness

References