Jump to content

Numerical 3-dimensional matching

From Wikipedia, the free encyclopedia

Numerical 3-dimensional matching is an NP-complete decision problem. It is given by three multisets of integers , and , each containing elements, and a bound . The goal is to select a subset of such that every integer in , and occurs exactly once and that for every triple in the subset holds. This problem is labeled as [SP16] in.[1]

Example

[edit]

Take , and , and . This instance has a solution, namely . Note that each triple sums to . The set is not a solution for several reasons: not every number is used (a is missing), a number is used too often (the ) and not every triple sums to (since ). 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 for the same , and , this problem would have no solution (all numbers sum to , which is not equal to in this case).

[edit]

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 , and , where there is an hyperedge if and only if . A matching in this hypergraph corresponds to a solution to ABC-partition.

Proof of NP-completeness

[edit]

The numerical 3-d matching problem is problem [SP16] of Garey and Johnson.[1] They claim it is NP-complete, and refer to,[2] but the claim is not proved at that source. The NP-hardness of the related problem 3-partition is done in [1] 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[3] 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[4] 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.

References

[edit]
  1. ^ a b c Garey, Michael R. and David S. Johnson (1979), Computers and Intractability; A Guide to the Theory of NP-Completeness. ISBN 0-7167-1045-5
  2. ^ Garey, M. R.; Johnson, D. S. (December 1975). "Complexity Results for Multiprocessor Scheduling under Resource Constraints". SIAM Journal on Computing. 4 (4): 397–411. doi:10.1137/0204035. ISSN 0097-5397.
  3. ^ Yu, Wenci; Hoogeveen, Han; Lenstra, Jan Karel (2004-09-01). "Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard". Journal of Scheduling. 7 (5): 333–348. doi:10.1023/B:JOSH.0000036858.59787.c2. ISSN 1099-1425.
  4. ^ Caracciolo, Sergio; Fichera, Davide; Sportiello, Andrea (2006-04-28), One-in-Two-Matching Problem is NP-complete, arXiv:cs/0604113, Bibcode:2006cs........4113C