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

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.

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", which references to this problem with the code [SP16].[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. 1 2 Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5
This article is issued from Wikipedia - version of the 10/15/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.