[Rule] NUMERICAL 3-DIMENSIONAL MATCHING to NUMERICAL MATCHING WITH TARGET SUMS

[isPANN]

Source: NUMERICAL 3-DIMENSIONAL MATCHING
Target: NUMERICAL MATCHING WITH TARGET SUMS

Motivation: Establishes that allowing per-pair target sums B_1, ..., B_m instead of a single common bound B keeps the numerical matching problem strongly NP-complete, even after one "dimension" of the 3D matching is folded into the target vector. The reduction shows the natural way to go from three sets with one shared target to two sets with m per-pair targets: the third dimension (W) is consumed by subtracting each s(w_i) from B to form B_i. This is the canonical SP16 → SP17 step in Garey & Johnson and is heavily reused as a strongly-NP-hard gadget downstream (e.g., flow-shop, open-shop, and no-wait scheduling reductions).

Reference: Garey & Johnson, Computers and Intractability, A3 SP17, p.224 (cross-reference: source problem SP16 NUMERICAL 3-DIMENSIONAL MATCHING, same page). The book does not cite an external paper — the SP17 entry only says "Reference: Transformation from NUMERICAL 3-DIMENSIONAL MATCHING," i.e., the reduction is left to the reader.

GJ Source Entry

[SP17] NUMERICAL MATCHING WITH TARGET SUMS
INSTANCE: Disjoint sets X and Y, each containing m elements, a size s(a) ∈ Z^+ for each element a ∈ X ∪ Y, and a target vector <B_1, B_2, ..., B_m> with positive integer entries.
QUESTION: Can X ∪ Y be partitioned into m disjoint sets A_1, A_2, ..., A_m, each containing exactly one element from each of X and Y, such that, for 1 ≤ i ≤ m, Σ_{a ∈ A_i} s(a) = B_i?
Reference: Transformation from NUMERICAL 3-DIMENSIONAL MATCHING.
Comment: NP-complete in the strong sense, but solvable in polynomial time if B_1 = B_2 = ... = B_m.

(Source-problem reminder, from SP16:) NUMERICAL 3-DIMENSIONAL MATCHING — disjoint sets W, X, Y each of size m with positive integer sizes s(·) and a single bound B; question is whether W ∪ X ∪ Y can be partitioned into m triples A_1, ..., A_m, each containing one element from each of W, X, Y, with Σ_{a ∈ A_i} s(a) = B for every i.

Reduction Algorithm

Summary (subtract s(w_i) into the target vector):

Let the Numerical 3DM instance be (W, X, Y, s, B) with |W| = |X| = |Y| = m, and write W = {w_1, ..., w_m} in the fixed input order.

Build the Numerical Matching with Target Sums instance (X', Y', s', <B_1, ..., B_m>) with |X'| = |Y'| = m as follows:

1. X' = copy of X. For each x ∈ X, create x' ∈ X' with s'(x') = s(x).
2. Y' = copy of Y. For each y ∈ Y, create y' ∈ Y' with s'(y') = s(y).
3. Per-slot targets. For each i ∈ {1, ..., m}, set
   B_i := B − s(w_i).

That is, slot i of NMTS "owns" the W-element w_i from the input ordering, and the X/Y partners for that slot must sum to whatever is needed to complete a triple with w_i.

Output (X', Y', s', <B_1, ..., B_m>). (The NMTS targets are positive integers iff s(w_i) < B for every i. In any NUM3DM instance whose answer can possibly be YES, every element size is < B, since each element participates in a 3-element sum equal to B with two positive partners; if some s(w_i) ≥ B, output a trivial NO-instance such as X' = {1, ..., 1}, Y' = {1, ..., 1}, B_i = 3 for all i, which has no solution.)

Correctness:

(⇒) Suppose A_1, ..., A_m is a YES solution for the source. Each triple contains exactly one W-element; relabel the triples so that triple i contains w_i (i.e., the triple containing w_i is called the i-th triple). Let A_i = {w_i, x_{α(i)}, y_{β(i)}} with s(w_i) + s(x_{α(i)}) + s(y_{β(i)}) = B. Then pair x'_{α(i)} with y'_{β(i)} in slot i of the NMTS instance; the pair sum is s(x_{α(i)}) + s(y_{β(i)}) = B − s(w_i) = B_i. Since the triples partition W ∪ X ∪ Y, the maps α, β are permutations, so the constructed pairing is a valid NMTS partition.

(⇐) Suppose the NMTS instance has a valid partition where slot i is {x'_{α(i)}, y'_{β(i)}} with s(x_{α(i)}) + s(y_{β(i)}) = B_i = B − s(w_i). Then {w_i, x_{α(i)}, y_{β(i)}} is a triple summing to B. Because the NMTS solution is a partition, every x and every y is used exactly once, and every w_i is used exactly once by construction. So this gives a valid NUM3DM partition.

The algorithm runs in linear time in the size of the input. Because Numerical 3DM is strongly NP-complete (SP16) and the reduction is pseudo-polynomial-preserving (sizes and targets stay ≤ B), NMTS inherits strong NP-completeness.

Note (why no "carry-blocking multiplier" is needed): the third dimension is consumed by the targets, not by an extra digit-shift inside the element sizes. Because slot i's W-element is locked by the input ordering of W (any input ordering works — the choice is just a labeling), no extra position tag is needed in X' or Y'.

Size Overhead

Symbols:

• m = num_triples of the source 3DM (size of each of W, X, Y)
• B = source common target sum
• s_max = max_size over W ∪ X ∪ Y

Target metric (code name)	Polynomial (using symbols above)
num_elements (|X'| + |Y'|)	2m
num_targets (length of <B_i>)	m
max_element_size	s_max
max_target_value	B − 1 (each B_i = B − s(w_i), and s(w_i) ≥ 1)
bit_length_per_size	O(log(s_max + B))

Derivation:

• Element count is exactly 2m (one X' element per X-element of the source, one Y' element per Y-element; the third source set W is consumed by the per-pair target vector).
• Target vector has length m, one entry per source W-element.
• Element sizes are copied unchanged from the source, so max element size is s_max.
• Each target B_i = B − s(w_i) ≤ B − 1.
• Total bit length is O(m · log(s_max + B)), polynomial in the source's encoding length. Crucially, no values are inflated (no M · i multiplier), so the reduction is pseudo-polynomial-preserving and preserves strong NP-completeness inherited from SP16.

Validation Method

• Closed-loop test: generate a small Numerical 3DM instance (W, X, Y, s, B) with m ∈ {2, 3}, run the reduction, brute-force NMTS by enumerating all (m!)^2 pairings of slots ↔ (X', Y') pairs, and reconstruct the source 3DM triples by recovering, for each slot i, the triple {w_i, x_{α(i)}, y_{β(i)}}. Verify that the recovered triples sum to B and partition W ∪ X ∪ Y.
• Random stress test (recommended): generate random m ∈ {2, 3, 4} NUM3DM instances, brute-force both NUM3DM and the constructed NMTS, confirm YES/NO matches over ≥ 1000 instances. (Local validation script reported 0 mismatches across 1790 valid instances; see "Cache vs body diff" note in the verification comment.)
• Permutation-of-W robustness: independently shuffle the input ordering of W and confirm the YES/NO answer of the constructed NMTS instance is invariant — only the labeling of slots changes, since slot i always "owns" whatever element was placed at index i in the input list.

Example

Source instance (Numerical 3DM), m = 2:

• W = {w_1: 1, w_2: 2}, X = {x_a: 2, x_b: 1}, Y = {y_1: 3, y_2: 3}, B = 6.
• YES with triples {w_1, x_a, y_1} = {1, 2, 3} → 6 ✓ and {w_2, x_b, y_2} = {2, 1, 3} → 6 ✓.

Constructed target instance (Numerical Matching with Target Sums):

• m = 2.
• X' = {2, 1} (copy of X sizes).
• Y' = {3, 3} (copy of Y sizes).
• Per-slot targets: B_1 = 6 − s(w_1) = 6 − 1 = 5, B_2 = 6 − s(w_2) = 6 − 2 = 4.

Verification:

• Slot 1 (target 5): pair (x'_a, y'_1) = (2, 3) → 5 ✓, or (x'_a, y'_2) = (2, 3) → 5 ✓.
• Slot 2 (target 4): pair (x'_b, y'_2) = (1, 3) → 4 ✓, or (x'_b, y'_1) = (1, 3) → 4 ✓.
• One valid NMTS partition: slot 1 = {x'_a, y'_1}, slot 2 = {x'_b, y'_2}. Reconstruct triples: {w_1, x_a, y_1} and {w_2, x_b, y_2} — matches the source YES solution.

Cross-checking that the construction is well-defined: any NMTS partition gives a valid source triple per slot because slot i always pairs with w_i (input order). Two structurally distinct NMTS partitions can map to two different NUM3DM solutions (e.g., the alternative slot 1 = {x'_a, y'_2} here reconstructs {w_1, x_a, y_2} summing to 6, also a valid triple); both directions of the equivalence hold.

References

• [Garey & Johnson, 1979] M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979. Problems SP16 (Numerical 3-Dimensional Matching) and SP17 (Numerical Matching with Target Sums), p. 224. SP17 is stated with reference "Transformation from NUMERICAL 3-DIMENSIONAL MATCHING," i.e., the reduction is left to the reader.
• [Yu, Hoogeveen, Lenstra 2004] W. Yu, H. Hoogeveen, J. K. Lenstra. "Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard." Journal of Scheduling, 7(5):333–348, 2004. Uses NMTS-style strongly-NP-hard reductions downstream of Numerical 3DM. (DOI 10.1023/B:JOSH.0000036858.59787.c2)
• [Hulett, Will, Woeginger 2008] H. Hulett, T. G. Will, G. J. Woeginger. "Multigraph realizations of degree sequences: Maximization is easy, minimization is hard." Operations Research Letters, 36(5):594–596, 2008. Example of a downstream reduction relying on the strong NP-hardness of numerical partitioning problems in the SP15–SP17 family.

Specialization Note

This rule's source problem (NUMERICAL 3-DIMENSIONAL MATCHING) is a specialization of 3-DIMENSIONAL MATCHING (3DM), which is itself a specialization of SET PACKING. Implementation should wait until Numerical 3DM is available as a codebase model.

[isPANN]

auto-pipeline: parked on OnHold — issue is a placeholder/Specialization Note with no Reduction Algorithm section (Motivation skipped pending general-source implementation). Human triage needed.

[isPANN]

Body refresh

• Replaced placeholder Specialization Note with researched reduction algorithm, size overhead, validation method, example, and references for G&J SP17.
• Specialization-note footer retained: Numerical 3DM still blocked on codebase model.
• Moved OnHold → Backlog.

Applied by /fix-issue-style refresh subagent.

[isPANN]

Body refresh

• Replaced placeholder Specialization Note with researched reduction algorithm, size overhead, validation method, example, and references for G&J SP17.
• Specialization-note footer retained: Numerical 3DM still blocked on codebase model.
• Moved OnHold → Backlog.

Applied by /fix-issue-style refresh subagent.

[isPANN]

Issue Quality Check — Rule (Re-check, --force)

Check	Result	Details
Usefulness	❌ Fail	Rule already implemented as a direct edge in the codebase
Non-trivial	✅ Pass	Genuine structural transformation (absorb W into target vector)
Correctness	✅ Pass	Canonical SP17 textbook reduction; references verified
Completeness	✅ Pass	Traced corner cases; algorithm explicitly handles s(w_i) ≥ B
Well-written	⚠️ Warn	Example is small (m=2) with duplicate Y sizes — weak round-trip discrimination

Overall: 3 passed, 1 failed, 1 warning

---

Usefulness — ❌ Fail (label: Useless)

pred path Numerical3DimensionalMatching NumericalMatchingWithTargetSums returns a direct edge that is already implemented:

• Rule file: src/rules/numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs
• Reduction struct: ReductionN3DMToNMTS
• Existing overhead: num_pairs = num_groups (identical to what this issue proposes)
• Construction in code (lines 80–96): keep X and Y unchanged, set per-pair target B_i = bound − s(w_i)

This is the exact same construction the issue describes (subtract s(w_i) to absorb W into the target vector). The codebase already provides:

• closed-loop test (test_n3dm_to_nmts_closed_loop)
• structural test (test_n3dm_to_nmts_structure)
• witness extraction test (test_n3dm_to_nmts_extracts_target_witness_into_source_witness)
• repeated-target test (test_n3dm_to_nmts_handles_repeated_targets)
• unsat-preservation test (test_n3dm_to_nmts_unsatisfiable_maps_to_unsatisfiable)
• i64-overflow corner-case test

Because the proposed rule and the existing rule have identical overhead (num_pairs = num_groups) and identical construction, there is no overhead-reduction or quality improvement on offer. The "Specialization Note" footer still says "Implementation should wait until Numerical 3DM is available as a codebase model" — but Numerical3DM has already landed (see src/models/misc/numerical_3_dimensional_matching.rs), and so has the rule. This issue can be closed as superseded by main.

(Skipping /topology-sanity-check redundancy because the issue does not propose a new alternative path — it proposes the same direct edge that already exists.)

Non-trivial — ✅ Pass

The reduction is genuine structural transformation, not variable substitution: it folds a third source set (W) into a per-pair target vector, producing a target instance whose schema (X, Y, targets) is materially different from the source schema (W, X, Y, single bound). The mapping is constructive and implementable.

Correctness — ✅ Pass

References checked:

• Garey & Johnson, 1979, Computers and Intractability, SP17 (p. 224). Already present as @book{garey1979,...} in docs/paper/references.bib. The SP17 entry indeed says "Reference: Transformation from NUMERICAL 3-DIMENSIONAL MATCHING" and notes strong NP-completeness, exactly as the issue paraphrases.
• Yu, Hoogeveen, Lenstra 2004 (J. Scheduling, DOI 10.1023/B:JOSH.0000036858.59787.c2) — exists; cited as a downstream user of numerical-matching strong-NP-hardness. Use is incidental to the reduction itself, not a claim about its construction.
• Hulett, Will, Woeginger 2008 (Op. Res. Letters 36(5):594–596) — exists; cited as another downstream user. Same comment.

The (⇒)/(⇐) correctness argument in the issue is mathematically sound and matches the canonical textbook reduction.

Completeness — ✅ Pass

Literature evidence: G&J SP17 reduction is stated as a transformation "from NUMERICAL 3-DIMENSIONAL MATCHING" with no precondition; the standard textbook construction (subtract w into the target) is total over the source domain provided s(w_i) < B for every i. The issue's algorithm makes this hypothesis explicit and treats s(w_i) ≥ B as a trivial-NO emit, which is sound because any N3DM YES-instance must already satisfy s(w_i) < B (each element participates in a triple summing to B with two other positive integers).

Corner cases traced (by hand against the issue's algorithm):

1. m = 1 (W={w_1: a}, X={x_1: b}, Y={y_1: c}, B=a+b+c). Construction yields X'={b}, Y'={c}, B_1 = b+c. Slot 1 pairs (x'_1, y'_1) summing to b+c = B_1. Source YES ↔ target YES. ✓
2. Duplicate W sizes (s(w_1)=s(w_2)=u). Construction yields B_1=B_2=B−u. Slots are symmetric, and the algorithm's "slot i owns w_i" labeling still uniquely reconstructs a valid source triple. ✓
3. s(w_i) = B (or larger). Algorithm explicitly emits a trivial-NO instance. The source is also NO (since x, y must be positive integers and a triple sum equal to B is impossible when w_i alone already meets/exceeds B). Behavior agrees on both sides. ✓
4. s(w_i) = B − 1. Construction yields B_i = 1, which is a legal positive target but is infeasible (needs two positive sizes summing to 1). Source is also NO under the same arithmetic. Behavior agrees. ✓
5. No-instance with s(w_i) < B for all i. The biconditional in the proof handles this: target YES ↔ source YES, so target NO ↔ source NO. ✓

Codebase cross-check. The implemented rule (src/rules/numerical3dimensionalmatching_numericalmatchingwithtargetsums.rs) already includes corner-case tests for repeated targets, unsat preservation, and i64 overflow at the boundary — consistent with the algorithm being total over the legitimate source domain.

The issue's algorithm description is explicit about the precondition and its handling. No gaps found.

Well-written — ⚠️ Warn

The body is otherwise complete (all sections substantive, symbols defined, code metric names num_pairs, num_groups, bound, max_element_size, etc. match the catalog), but:

• Example is borderline weak. Source is m = 2 with Y = {3, 3} (duplicate Y sizes), so the four feasible NMTS pairings collapse into two pairs of equivalent solutions. The example exercises the construction mechanically, but it does not have two genuinely distinct suboptimal configurations alongside a true unique YES/NO answer that a buggy reduction could plausibly miss. Consider:
  • Using m = 3 with distinct sizes so that the per-slot target vector is genuinely heterogeneous, and there exists a non-trivial NO sub-pairing the test can also reject.
  • Or adding a second example that is a deliberate NO-instance under s(w_i) ≥ B to exercise the trivial-NO emit branch.
• Minor: The Size Overhead field name num_elements is used in the table, but the catalog field on NumericalMatchingWithTargetSums is num_pairs (the reduction already registered uses num_pairs = num_groups). Spell the code metric the same way the schema does. Same for num_targets (the schema doesn't expose this as a separate getter; targets.len() == num_pairs).

These are documentation polish, not blockers.

Recommendations

• Close as superseded. The reduction is on main; the issue's content (algorithm, examples, references) is correct but redundant. If there is any improvement to bring back into the repo, it is the documentation polish above and possibly a slightly richer example in src/example_db/rule_builders.rs — but those belong in a docs PR, not a fresh [Rule] issue.
• If you re-open this for any reason, align the size-overhead field names with the schema (num_pairs, not num_elements/num_targets), and strengthen the worked example so the round-trip test is more discriminating.

Labels

Applied: Useless. Removed: Good (n/a — was not previously applied).