Source: 3-DIMENSIONAL MATCHING (3DM)
Target: NUMERICAL 3-DIMENSIONAL MATCHING (Numerical3DM)
Motivation: Establishes NP-completeness — in the strong sense — of NUMERICAL 3-DIMENSIONAL MATCHING, the canonical number-partitioning matching problem in Garey & Johnson and the gateway to SP17–SP19 (e.g., 3-PARTITION). The standard reduction from 3DM uses a positional digit encoding with base r = m + 1 (where m = |M| is the number of source triples), so that no carries occur when up to m sizes are summed. The combinatorial "one element from each of X̂, Ŷ, Ẑ" constraint becomes the arithmetic constraint that every group of three numbers (one from W, X, Y) sums to a common bound B. Strong NP-completeness follows because every numeric value built has bit length O((q + m) log m), polynomial in the input — so the reduction remains polynomial even when sizes are written in unary. This is the textbook bridge from combinatorial hardness to arithmetic / scheduling hardness.
Reference: Garey & Johnson, Computers and Intractability, problem SP16 (p. 224). The G&J entry cites "Transformation from 3-DIMENSIONAL MATCHING (see proof of Theorem 4.4)" — the proof of Theorem 4.4 originally appears in M. R. Garey and D. S. Johnson, "Complexity Results for Multiprocessor Scheduling under Resource Constraints," SIAM J. Comput. 4 (1975), 397–411. 3DM hardness is from Karp (1972).
GJ Source Entry
[SP16] NUMERICAL 3-DIMENSIONAL MATCHING
INSTANCE: Disjoint sets W, X, and Y, each containing m elements, a size s(a) ∈ Z+ for each element a ∈ W ∪ X ∪ Y, and a bound B ∈ Z+.
QUESTION: Can W ∪ X ∪ Y be partitioned into m disjoint sets A_1, A_2, ..., A_m such that each A_i contains exactly one element from each of W, X, and Y and such that, for 1 ≤ i ≤ m, ∑_{a ∈ A_i} s(a) = B?
Reference: [Garey and Johnson, 1979]. Transformation from 3-DIMENSIONAL MATCHING (see proof of Theorem 4.4 in Garey & Johnson, SIAM J. Comput. 4 (1975)).
Comment: NP-complete in the strong sense (remains NP-complete when sizes are written in unary, equivalently when sizes are bounded by a polynomial in the input length).
Reduction Algorithm
Summary:
Let the source 3DM instance have element sets X̂, Ŷ, Ẑ with |X̂| = |Ŷ| = |Ẑ| = q and a collection M ⊆ X̂ × Ŷ × Ẑ of source triples; assume without loss of generality that m := |M| ≥ q (otherwise no perfect 3-matching exists and we output a trivial NO Numerical3DM instance). We build a Numerical3DM instance with |W| = |X| = |Y| = m.
-
Base. Pick r := m + 1. Then for any subset of at most m of the constructed sizes, base-r digit-wise addition never carries (each digit is at most m < r). This is the standard carry-free trick used in 3DM-to-arithmetic reductions.
-
Digit layout. Reserve digit positions in base r for two roles:
- Coordinate positions
0, 1, …, 3q − 1 — one per element of X̂ ∪ Ŷ ∪ Ẑ: positions [0..q-1] index X̂, [q..2q-1] index Ŷ, [2q..3q-1] index Ẑ.
- Tag positions
3q, 3q+1, …, 3q+m−1 — one per source triple index k = 1, …, m. These are the "glue" digits that force the W-, X-, Y-elements of each output group to come from the same source triple.
-
One source triple → three target elements. For each source triple t_k = (x_{i_k}, y_{j_k}, z_{l_k}) ∈ M (k = 1, …, m), introduce a W-element w_k, an X-element x'_k, and a Y-element y'_k. Their sizes encode the source triple in the coordinate block and share a common tag pattern at the k-th tag position. Concretely, every size is a sum of distinct powers of r — i.e., a 0/1 digit pattern at the chosen positions. The W-element carries the X̂-coordinate digit, the X-element carries the Ŷ-coordinate digit, the Y-element carries the Ẑ-coordinate digit; additional "tag" digits at position 3q + k − 1 are arranged so that the only way s(w_a) + s(x'_b) + s(y'_c) can match the target tag pattern at position 3q + k − 1 for every k simultaneously is to have all three picks come from the same source-triple index. (Several equivalent tag arrangements appear in the literature — Garey & Johnson, SP16 / Thm 4.4 give one; the construction can also be derived by reducing to SUBSET SUM with base m+1 and then "splitting" each summand into three using fresh tag digits. The essential property is carry-freeness plus a tag pattern that is realizable only by same-index triples.)
-
Bound B. Set the digit pattern of B so that, summed over all m output groups, each coordinate position is hit exactly once (digit 1) and each tag position is hit by exactly the per-group tag contribution from a valid same-index group. Then ∑_{a ∈ W ∪ X ∪ Y} s(a) = m · B by construction, which is a necessary condition for an equal-sum partition.
-
Output (W, X, Y, s, B) with |W| = |X| = |Y| = m.
Correctness sketch.
(⇒) If M itself has been padded so that some q-subset of triples forms a 3-matching of the original 3DM instance, then in the constructed Numerical3DM instance the partition A_k = {w_k, x'_k, y'_k} (k = 1, …, m) has every coordinate digit hit exactly once across the m groups and matches B per group by the choice of tag values.
(⇐) Suppose A_1, …, A_m is a sum-B partition. Because base r = m + 1 precludes carries, the tag-position constraint at every position 3q + k − 1 can only be satisfied by groups whose three members share index k; hence each A_i = {w_{σ(i)}, x'_{σ(i)}, y'_{σ(i)}} for some permutation σ of {1, …, m}. The coordinate-position constraints then say each X̂-, Ŷ-, Ẑ-element is hit exactly once across all m groups, which decodes to a perfect 3-matching of the source instance.
The construction is polynomial: each size has digit length O(q + m) in base r = m + 1, i.e., bit length O((q + m) log m); and there are exactly 3m target elements. Strong NP-completeness follows directly: max s(a) and B are bounded by r^{3q + m} = (m + 1)^{O(q + m)}, so even the unary-encoded numeric input has length polynomial in q + m.
Size Overhead
Symbols:
q = |X̂| = |Ŷ| = |Ẑ| in the source 3DM instancem = |M| = num_triples in the source (assume m ≥ q after optional padding)r = m + 1 (encoding base)
| Target metric (code name) |
Polynomial (using symbols above) |
num_elements (= ` |
W |
bound_B (numeric value) |
O((m + 1)^{3q + m}) |
max_weight (largest s(a)) |
O((m + 1)^{3q + m − 1}) |
| Bit length of any single size |
O((q + m) · log m) |
| Total instance size (bits) |
O(m · (q + m) · log m) |
Derivation:
- Each source triple contributes three target elements (one each in W, X, Y);
|W| = |X| = |Y| = m, total 3m.
- The numeric values of
B and the sizes are dominated by the highest digit at position 3q + m − 1 in base r = m + 1, giving O((m + 1)^{3q + m}).
- Critically, while
B is exponential as a number, its bit length is O((q + m) log m) — polynomial in the input. This is what makes the reduction polynomial-time and Numerical3DM strongly NP-complete.
Implementer note: store sizes as big integers (or guard (3q + m) · log2(m + 1) ≤ 63 if using i64). The reduction is polynomial in input bits but the numeric values grow exponentially with q + m.
Validation Method
- Closed-loop test. Reduce a small 3DM YES instance to Numerical3DM, solve the target by brute force (enumerate all partitions of
W ∪ X ∪ Y into m one-per-side triples, check each triple sums to B), then recover the source matching by reading off the (X̂, Ŷ, Ẑ) coordinate digits encoded in each group. Verify the result is a valid 3-matching.
- 3DM NO instance. Pick a 3-matching-infeasible triple set (e.g.,
q = 2 with M = {(1,1,1), (2,2,2), (1,2,1)} where no two disjoint triples exist). The constructed Numerical3DM should brute-force to "no equal-sum partition exists."
- No-carry sanity check. Verify by base-
r arithmetic that summing any m constructed sizes never overflows a digit position (every digit ≤ m < r).
- Aggregate check. Confirm
∑_{a} s(a) = m · B exactly — a necessary condition for any equal-sum partition.
- Round-trip witness check. Apply
extract_solution to the Numerical3DM witness, confirm it is a valid 3DM matching of the original instance, and check its objective is optimal under brute force.
Example (schematic)
A fully numeric q = 2, m = 2 example would need the exact tag values from the construction in G&J SP16 / Thm 4.4 (SIAM J. Comput. 4 (1975)). Rather than risk arithmetic that does not balance to a single B, we describe only the structural picture and defer the concrete tag values to the implementation:
Source instance (3DM). X̂ = Ŷ = Ẑ = {1, 2}, so q = 2. M = { t_1 = (1, 1, 1), t_2 = (2, 2, 2) }, so m = 2. (YES: M itself is a 3-matching.)
Construction skeleton.
- Base
r = m + 1 = 3.
- Coordinate positions:
0..1 for X̂, 2..3 for Ŷ, 4..5 for Ẑ. Tag positions: 6 for t_1, 7 for t_2. Total 3q + m = 8 digit positions.
- For each
t_k = (x_{i_k}, y_{j_k}, z_{l_k}), the three sizes s(w_k), s(x'_k), s(y'_k) each carry one coordinate digit (at the X̂-, Ŷ-, Ẑ-position respectively) plus a tag digit at position 3q + k − 1. Total target instance: |W| = |X| = |Y| = m = 2.
- The bound
B is the digit pattern that has a 1 in every coordinate position and the per-group tag contribution in every tag position.
The numeric tag values come from G&J SP16 (Theorem 4.4 in the 1975 SIAM paper) and should be transcribed verbatim by the implementer; see also the analogous "subset sum" derivation in Verschelde's lecture notes (UIC MCS 401, "Partitioning and Numerical Problems") and the carry-free base = m + 1 discussion on the Wikipedia article for 3-Dimensional Matching.
References
- [Garey & Johnson, 1979] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Problem SP16 (NUMERICAL 3-DIMENSIONAL MATCHING), p. 224.
- [Garey & Johnson, 1975] Michael R. Garey and David S. Johnson. "Complexity Results for Multiprocessor Scheduling under Resource Constraints." SIAM Journal on Computing 4 (1975), 397–411. (Original proof of Theorem 4.4 referenced by SP16.)
- [Karp, 1972] Richard M. Karp. "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, pp. 85–103. Plenum Press, 1972. (Original 3DM NP-completeness.)
- [Wikipedia: Numerical 3-dimensional matching] https://en.wikipedia.org/wiki/Numerical_3-dimensional_matching — confirms
[SP16] classification and strongly-NP-complete categorization; cites Yu, Hoogeveen & Lenstra (2004) and Caracciolo, Fichera & Sportiello (2006) for alternate hardness proofs.
- [Wikipedia: 3-dimensional matching] https://en.wikipedia.org/wiki/3-dimensional_matching — confirms the carry-free
base = 1 + m encoding used in 3DM → arithmetic reductions.
- [Verschelde notes] Jan Verschelde, "Partitioning and Numerical Problems," UIC MCS 401, http://homepages.math.uic.edu/~jan/mcs401/partitioning.pdf — walks through base-
m+1 digit encoding for the analogous 3DM → SUBSET SUM reduction.
- [Toronto CSC 373 notes] "SUBSET SUM," http://www.cs.toronto.edu/~lalla/373s16/notes/SS.pdf — same base-
m+1, 3q-digit construction.
Specialization Note
This rule's source problem (3-DIMENSIONAL MATCHING / 3DM) is a specialization of SET PACKING (MaximumSetPacking). Implementation should wait until 3DM is available as a codebase model.
Source: 3-DIMENSIONAL MATCHING (3DM)
Target: NUMERICAL 3-DIMENSIONAL MATCHING (Numerical3DM)
Motivation: Establishes NP-completeness — in the strong sense — of NUMERICAL 3-DIMENSIONAL MATCHING, the canonical number-partitioning matching problem in Garey & Johnson and the gateway to SP17–SP19 (e.g., 3-PARTITION). The standard reduction from 3DM uses a positional digit encoding with base
r = m + 1(wherem = |M|is the number of source triples), so that no carries occur when up tomsizes are summed. The combinatorial "one element from each of X̂, Ŷ, Ẑ" constraint becomes the arithmetic constraint that every group of three numbers (one from W, X, Y) sums to a common boundB. Strong NP-completeness follows because every numeric value built has bit length O((q + m) log m), polynomial in the input — so the reduction remains polynomial even when sizes are written in unary. This is the textbook bridge from combinatorial hardness to arithmetic / scheduling hardness.Reference: Garey & Johnson, Computers and Intractability, problem SP16 (p. 224). The G&J entry cites "Transformation from 3-DIMENSIONAL MATCHING (see proof of Theorem 4.4)" — the proof of Theorem 4.4 originally appears in M. R. Garey and D. S. Johnson, "Complexity Results for Multiprocessor Scheduling under Resource Constraints," SIAM J. Comput. 4 (1975), 397–411. 3DM hardness is from Karp (1972).
GJ Source Entry
Reduction Algorithm
Summary:
Let the source 3DM instance have element sets X̂, Ŷ, Ẑ with
|X̂| = |Ŷ| = |Ẑ| = qand a collection M ⊆ X̂ × Ŷ × Ẑ of source triples; assume without loss of generality thatm := |M| ≥ q(otherwise no perfect 3-matching exists and we output a trivial NO Numerical3DM instance). We build a Numerical3DM instance with|W| = |X| = |Y| = m.Base. Pick
r := m + 1. Then for any subset of at mostmof the constructed sizes, base-rdigit-wise addition never carries (each digit is at mostm < r). This is the standard carry-free trick used in 3DM-to-arithmetic reductions.Digit layout. Reserve digit positions in base
rfor two roles:0, 1, …, 3q − 1— one per element of X̂ ∪ Ŷ ∪ Ẑ: positions[0..q-1]index X̂,[q..2q-1]index Ŷ,[2q..3q-1]index Ẑ.3q, 3q+1, …, 3q+m−1— one per source triple indexk = 1, …, m. These are the "glue" digits that force the W-, X-, Y-elements of each output group to come from the same source triple.One source triple → three target elements. For each source triple
t_k = (x_{i_k}, y_{j_k}, z_{l_k}) ∈ M(k = 1, …, m), introduce a W-elementw_k, an X-elementx'_k, and a Y-elementy'_k. Their sizes encode the source triple in the coordinate block and share a common tag pattern at the k-th tag position. Concretely, every size is a sum of distinct powers ofr— i.e., a 0/1 digit pattern at the chosen positions. The W-element carries the X̂-coordinate digit, the X-element carries the Ŷ-coordinate digit, the Y-element carries the Ẑ-coordinate digit; additional "tag" digits at position3q + k − 1are arranged so that the only ways(w_a) + s(x'_b) + s(y'_c)can match the target tag pattern at position3q + k − 1for every k simultaneously is to have all three picks come from the same source-triple index. (Several equivalent tag arrangements appear in the literature — Garey & Johnson, SP16 / Thm 4.4 give one; the construction can also be derived by reducing to SUBSET SUM with basem+1and then "splitting" each summand into three using fresh tag digits. The essential property is carry-freeness plus a tag pattern that is realizable only by same-index triples.)Bound B. Set the digit pattern of
Bso that, summed over allmoutput groups, each coordinate position is hit exactly once (digit 1) and each tag position is hit by exactly the per-group tag contribution from a valid same-index group. Then∑_{a ∈ W ∪ X ∪ Y} s(a) = m · Bby construction, which is a necessary condition for an equal-sum partition.Output
(W, X, Y, s, B)with|W| = |X| = |Y| = m.Correctness sketch.
(⇒) If M itself has been padded so that some
q-subset of triples forms a 3-matching of the original 3DM instance, then in the constructed Numerical3DM instance the partitionA_k = {w_k, x'_k, y'_k}(k = 1, …, m) has every coordinate digit hit exactly once across the m groups and matchesBper group by the choice of tag values.(⇐) Suppose
A_1, …, A_mis a sum-Bpartition. Because baser = m + 1precludes carries, the tag-position constraint at every position3q + k − 1can only be satisfied by groups whose three members share indexk; hence eachA_i = {w_{σ(i)}, x'_{σ(i)}, y'_{σ(i)}}for some permutation σ of{1, …, m}. The coordinate-position constraints then say each X̂-, Ŷ-, Ẑ-element is hit exactly once across all m groups, which decodes to a perfect 3-matching of the source instance.The construction is polynomial: each size has digit length
O(q + m)in baser = m + 1, i.e., bit lengthO((q + m) log m); and there are exactly3mtarget elements. Strong NP-completeness follows directly:max s(a)andBare bounded byr^{3q + m} = (m + 1)^{O(q + m)}, so even the unary-encoded numeric input has length polynomial inq + m.Size Overhead
Symbols:
q=|X̂|=|Ŷ|=|Ẑ|in the source 3DM instancem=|M|=num_triplesin the source (assumem ≥ qafter optional padding)r=m + 1(encoding base)num_elements(= `bound_B(numeric value)O((m + 1)^{3q + m})max_weight(largests(a))O((m + 1)^{3q + m − 1})O((q + m) · log m)O(m · (q + m) · log m)Derivation:
|W| = |X| = |Y| = m, total3m.Band the sizes are dominated by the highest digit at position3q + m − 1in baser = m + 1, givingO((m + 1)^{3q + m}).Bis exponential as a number, its bit length isO((q + m) log m)— polynomial in the input. This is what makes the reduction polynomial-time and Numerical3DM strongly NP-complete.Implementer note: store sizes as big integers (or guard
(3q + m) · log2(m + 1) ≤ 63if usingi64). The reduction is polynomial in input bits but the numeric values grow exponentially withq + m.Validation Method
W ∪ X ∪ Yinto m one-per-side triples, check each triple sums toB), then recover the source matching by reading off the (X̂, Ŷ, Ẑ) coordinate digits encoded in each group. Verify the result is a valid 3-matching.q = 2withM = {(1,1,1), (2,2,2), (1,2,1)}where no two disjoint triples exist). The constructed Numerical3DM should brute-force to "no equal-sum partition exists."rarithmetic that summing anymconstructed sizes never overflows a digit position (every digit ≤m < r).∑_{a} s(a) = m · Bexactly — a necessary condition for any equal-sum partition.extract_solutionto the Numerical3DM witness, confirm it is a valid 3DM matching of the original instance, and check its objective is optimal under brute force.Example (schematic)
A fully numeric
q = 2,m = 2example would need the exact tag values from the construction in G&J SP16 / Thm 4.4 (SIAM J. Comput.4 (1975)). Rather than risk arithmetic that does not balance to a singleB, we describe only the structural picture and defer the concrete tag values to the implementation:Source instance (3DM).
X̂ = Ŷ = Ẑ = {1, 2}, soq = 2.M = { t_1 = (1, 1, 1), t_2 = (2, 2, 2) }, som = 2. (YES:Mitself is a 3-matching.)Construction skeleton.
r = m + 1 = 3.0..1for X̂,2..3for Ŷ,4..5for Ẑ. Tag positions:6fort_1,7fort_2. Total3q + m = 8digit positions.t_k = (x_{i_k}, y_{j_k}, z_{l_k}), the three sizess(w_k), s(x'_k), s(y'_k)each carry one coordinate digit (at the X̂-, Ŷ-, Ẑ-position respectively) plus a tag digit at position3q + k − 1. Total target instance:|W| = |X| = |Y| = m = 2.Bis the digit pattern that has a 1 in every coordinate position and the per-group tag contribution in every tag position.The numeric tag values come from G&J SP16 (Theorem 4.4 in the 1975 SIAM paper) and should be transcribed verbatim by the implementer; see also the analogous "subset sum" derivation in Verschelde's lecture notes (UIC MCS 401, "Partitioning and Numerical Problems") and the carry-free
base = m + 1discussion on the Wikipedia article for 3-Dimensional Matching.References
[SP16]classification and strongly-NP-complete categorization; cites Yu, Hoogeveen & Lenstra (2004) and Caracciolo, Fichera & Sportiello (2006) for alternate hardness proofs.base = 1 + mencoding used in 3DM → arithmetic reductions.m+1digit encoding for the analogous 3DM → SUBSET SUM reduction.m+1,3q-digit construction.Specialization Note
This rule's source problem (3-DIMENSIONAL MATCHING / 3DM) is a specialization of SET PACKING (MaximumSetPacking). Implementation should wait until 3DM is available as a codebase model.