Numerical 3-dimensional matching

Take $X=\backslash \{3,4,4\backslash \}$, $Y=\backslash \{1,4,6\backslash \}$ and $Z=\backslash \{1,2,5\backslash \}$, and $b=10$. This instance has a solution, namely $\backslash \{(3,6,1),\; (4,4,2),\; (4,1,5)\backslash \}$. Note that each triple sums to $b=10$. The set $\backslash \{(3,6,1),\; (3,4,2),\; (4,1,5)\backslash \}$ is not a solution for several reasons: not every number is used (a $4\backslash in\; X$ is missing), a number is used too often (the $3\backslash in\; X$) and not every triple sums to $b$ (since $3+4+2=9\backslash 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\backslash cdot\; b=33$ in this case).

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 {{tmath|(x, y, z)}} if and only if $x+y+z\; =\; T$. A matching in this hypergraph corresponds to a solution to ABC-partition.

The numerical 3-d matching problem is problem [SP16] of Garey and Johnson. They claim it is NP-complete, and refer to,{{Cite journal |last1=Garey |first1=M. R. |last2=Johnson |first2=D. S. |date=December 1975 |title=Complexity Results for Multiprocessor Scheduling under Resource Constraints |url=http://epubs.siam.org/doi/10.1137/0204035 |journal=SIAM Journal on Computing |language=en |volume=4 |issue=4 |pages=397–411 |doi=10.1137/0204035 |issn=0097-5397|url-access=subscription }} 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{{Cite journal |last1=Yu |first1=Wenci |last2=Hoogeveen |first2=Han |last3=Lenstra |first3=Jan Karel |date=2004-09-01 |title=Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard |url=https://doi.org/10.1023/B:JOSH.0000036858.59787.c2 |journal=Journal of Scheduling |language=en |volume=7 |issue=5 |pages=333–348 |doi=10.1023/B:JOSH.0000036858.59787.c2 |issn=1099-1425}} 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{{Citation |last1=Caracciolo |first1=Sergio |title=One-in-Two-Matching Problem is NP-complete |date=2006-04-28 |last2=Fichera |first2=Davide |last3=Sportiello |first3=Andrea|arxiv=cs/0604113 |bibcode=2006cs........4113C }} 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.

{{reflist}}

Category:Strongly NP-complete problems