[Model] ThreeDimensionalMatching

[isPANN]

Motivation

3-DIMENSIONAL MATCHING (3DM) (P128) from Garey & Johnson, A3 SP1. One of Karp's 21 NP-complete problems, 3DM is a foundational problem for reductions to partitioning and scheduling problems. It occupies a central position in the G&J reduction hierarchy, serving as the source for many strong NP-completeness proofs.

Associated rules:

• As source: [Rule] 3-DIMENSIONAL MATCHING to 3-PARTITION #389/[Rule] 3-DIMENSIONAL MATCHING to 3-PARTITION #824 (→ 3-Partition), [Rule] 3-DIMENSIONAL MATCHING to NUMERICAL 3-DIMENSIONAL MATCHING #390/[Rule] 3-DIMENSIONAL MATCHING to NUMERICAL 3-DIMENSIONAL MATCHING #826 (→ Num3DM), [Rule] 3-DIMENSIONAL MATCHING to 3-MATROID INTERSECTION #386/[Rule] 3-DIMENSIONAL MATCHING to 3-MATROID INTERSECTION #857 (→ 3-Matroid Intersection), [Rule] 3-DIMENSIONAL MATCHING to MINIMUM BROADCAST TIME #378 (→ MinBroadcastTime), [Rule] 3-DIMENSIONAL MATCHING to PRUNED TRIE SPACE MINIMIZATION #398 (→ PrunedTrie), [Rule] 3-DIMENSIONAL MATCHING to MinimumMetricDimension #877 (→ MetricDimension), [Rule] 3-Dimensional Matching to MinimumWeightDecoding #916 (→ MinWeightDecoding)
• As target: 3SAT → 3DM (Karp, 1972; Section 3.1.2 of G&J)

Definition

Name: ThreeDimensionalMatching
Reference: Garey & Johnson, Computers and Intractability, A3 SP1

Mathematical definition:

INSTANCE: Set M ⊆ W×X×Y, where W, X, and Y are disjoint sets having the same number q of elements.
QUESTION: Does M contain a matching, i.e., a subset M' ⊆ M such that |M'| = q and no two elements of M' agree in any coordinate?

Variables

• Count: m = |M| (one binary variable per candidate triple)
• Per-variable domain: {0, 1} — 0 means the triple is excluded, 1 means it is selected
• Meaning: x_i = 1 if triple t_i ∈ M is included in the matching M'. A valid matching requires exactly q selected triples, each covering a distinct element from W, X, and Y.

Schema (data type)

Type name: ThreeDimensionalMatching
Variants: none

Field	Type	Description
universe_size	usize	q =
triples	Vec<(usize, usize, usize)>	Candidate triples (w, x, y) where w ∈ {0..q-1}, x ∈ {0..q-1}, y ∈ {0..q-1}

Notes:

• This is a feasibility (decision) problem: Value = Or.
• Key getter methods: universe_size() (= q), num_triples() (= |M|).
• W, X, Y are implicitly {0, ..., q-1}; no need to store them explicitly.

Complexity

• Decision complexity: NP-complete (Karp, 1972; transformation from 3SAT). Remains NP-complete when no element occurs in more than 3 triples. Solvable in polynomial time when no element occurs in more than 2 triples.
• Best known exact algorithm: O*(2^m) by brute-force enumeration of all subsets of size q from the m triples. No significantly faster exact algorithm is known for the general case.
• Concrete complexity expression: "2^num_triples" (for declare_variants!)
• Related: 2-Dimensional Matching (M ⊆ W×X) is solvable in polynomial time.
• References:
  • R.M. Karp (1972). "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, pp. 85-103.
  • M.R. Garey and D.S. Johnson (1979). Computers and Intractability. W.H. Freeman.

Extra Remark

Full book text:

INSTANCE: Set M ⊆ W×X×Y, where W, X, and Y are disjoint sets having the same number q of elements.
QUESTION: Does M contain a matching, i.e., a subset M' ⊆ M such that |M'| = q and no two elements of M' agree in any coordinate?
Reference: [Karp, 1972]. Transformation from 3SAT (see Section 3.1.2).
Comment: Remains NP-complete if M is "pairwise consistent," i.e., if for all elements a, b, c, whenever there exist elements w, z, and y such that (a,b,w) ∈ M, (a,x,c) ∈ M, and (y,b,c) ∈ M, then (a,b,c) ∈ M (this follows from the proof of Theorem 3.1.2). Also remains NP-complete if no element occurs in more than three triples, but is solvable in polynomial time if no element occurs in more than two triples [Garey and Johnson, ——]. The related 2-DIMENSIONAL MATCHING problem (where M ⊆ W×X) is also solvable in polynomial time (e.g., see [Lawler, 1976a]).

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all subsets of triples of size q; check if any forms a perfect matching.)
• It can be solved by reducing to integer programming. (Binary ILP: x_i ∈ {0,1} for each triple, Σ x_i = q, and for each element in W/X/Y, the sum of x_i over triples containing that element equals 1. Companion rule issue to be filed separately.)
• Other: (none known beyond brute force and ILP)

Example Instance

Input:
W = X = Y = {0, 1, 2} (q = 3)
Triples (m = 5):

• t_0 = (0, 1, 2)
• t_1 = (1, 0, 1)
• t_2 = (2, 2, 0)
• t_3 = (0, 0, 0)
• t_4 = (1, 2, 2)

Valid matching: M' = {t_0, t_1, t_2} = {(0,1,2), (1,0,1), (2,2,0)}:

• W elements: {0, 1, 2} — all distinct ✓
• X elements: {1, 0, 2} — all distinct ✓
• Y elements: {2, 1, 0} — all distinct ✓

Answer: YES — this is the unique valid matching (1 out of C(5,3) = 10 subsets of size 3).

Non-trivial structure: The other 9 size-3 subsets all fail. For example:

• {t_1, t_2, t_3} = {(1,0,1), (2,2,0), (0,0,0)}: X = {0, 2, 0} ✗ (element 0 repeated)
• {t_0, t_2, t_4} = {(0,1,2), (2,2,0), (1,2,2)}: X = {1, 2, 2} ✗ (element 2 repeated)

Negative modification: Remove t_2 = (2,2,0). Now M = {t_0, t_1, t_3, t_4}. The only size-3 subsets are {t_0,t_1,t_3}, {t_0,t_1,t_4}, {t_0,t_3,t_4}, {t_1,t_3,t_4} — none has all three W-coordinates distinct (W-coordinates of t_3 and t_0 both equal 0; t_1 and t_4 both equal 1). Answer: NO.

Python validation script

from itertools import combinations

triples = [(0,1,2), (1,0,1), (2,2,0), (0,0,0), (1,2,2)]
q = 3

# Positive: find all valid matchings
valid = []
for combo in combinations(range(len(triples)), q):
    sel = [triples[i] for i in combo]
    ws = [t[0] for t in sel]
    xs = [t[1] for t in sel]
    ys = [t[2] for t in sel]
    if len(set(ws)) == q and len(set(xs)) == q and len(set(ys)) == q:
        valid.append(combo)

assert len(valid) == 1
assert valid[0] == (0, 1, 2)
print(f"Positive: {len(valid)}/10 valid matchings (unique)")

# Negative: remove t2
triples_neg = [(0,1,2), (1,0,1), (0,0,0), (1,2,2)]
valid_neg = []
for combo in combinations(range(len(triples_neg)), q):
    sel = [triples_neg[i] for i in combo]
    ws = [t[0] for t in sel]
    xs = [t[1] for t in sel]
    ys = [t[2] for t in sel]
    if len(set(ws)) == q and len(set(xs)) == q and len(set(ys)) == q:
        valid_neg.append(combo)

assert len(valid_neg) == 0
print(f"Negative: {len(valid_neg)}/4 valid matchings (correct: NO)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; strong reduction connectivity planned
Non-trivial	✅ Pass	Distinct from all existing problems including ExactCoverBy3Sets
Correctness	✅ Pass	References verified; complexity claim is honest about brute-force bound
Well-written	❌ Fail	Missing ILP companion issue link; example has false-start clutter; complexity lacks concrete expression

Overall: 3 passed, 0 warnings, 1 failed

---

Usefulness

Pass. ThreeDimensionalMatching does not exist in the codebase (pred show fails). The issue lists extensive planned reductions — as source for Partition, Num3DM, 3Partition, and many others, and as target from 3SAT. This is one of Karp's 21 NP-complete problems and occupies a central position in the G&J reduction hierarchy. Motivation is concrete and well-articulated. Both brute-force and ILP solver paths are identified.

Non-trivial

Pass. While related to ExactCoverBy3Sets (X3C), 3DM is structurally distinct: X3C has a universe and a collection of 3-element subsets, while 3DM has three disjoint sets W, X, Y and triples from their Cartesian product with coordinate-wise disjointness constraints. The feasibility constraint (no two selected triples agree in any coordinate) is genuinely different from exact cover (every element covered exactly once). These are separate problems connected by a non-trivial reduction (Exact Cover → 3DM is a known Karp reduction).

Correctness

Pass. Both references are real and well-known:

• Karp, 1972 — "Reducibility Among Combinatorial Problems" — confirmed; 3DM is problem Improve test coverage to match Julia UnitDiskMapping #17 of Karp's 21 NP-complete problems. Already in docs/paper/references.bib as karp1972.
• Garey & Johnson, 1979 — Computers and Intractability — confirmed; 3DM is listed as A3 SP1. The claim that NP-completeness follows from transformation from 3SAT (Section 3.1.2) matches the literature.
• The claim that the problem remains NP-complete when no element occurs in more than 3 triples, and is solvable in polynomial time when no element occurs in more than 2 triples, is a well-known result from Garey & Johnson.
• The complexity bound "O*(2^m)" is a generic brute-force bound — the issue honestly states "No significantly faster exact algorithm is known for the general decision problem." This is accurate.

Recommendation: The complexity section should provide a concrete expression suitable for declare_variants!. Since the brute-force approach is C(m, q) subsets, and in the worst case m can be up to q^3, a reasonable expression would be 2^num_triples. This is needed for implementation.

Well-written

Fail. Several issues need attention:

1. Missing ILP companion issue link (Fail). The "How to solve" section checks ILP solvability and describes the ILP formulation, but no [Rule] ThreeDimensionalMatching to ILP companion issue is linked in the body. Per template requirements, if direct ILP solving is claimed, a companion rule issue must be linked.

2. Example has false-start clutter (Fail). The example section contains a failed first attempt with inline corrections ("✗ — Y element 1 appears twice", "Let me redesign"). This is confusing and unprofessional. The example should present only the final revised instance cleanly, without the debugging trail. The revised example itself is correct — M' = {(0,1,2), (1,0,1), (2,2,0)} is indeed a valid perfect matching — but the presentation needs cleanup.

3. Complexity lacks concrete expression (Fail). The Complexity section says "O*(C(m,q)) ≈ O*(2^m)" but does not provide a concrete complexity expression in terms of problem parameters (e.g., 2^num_triples) as required by the template. This expression is needed for declare_variants!.

4. Schema redundancy (minor). The set_w, set_x, set_y fields are redundant since they are just {0, ..., q-1} — the universe_size field already fully determines them. Consider removing them and only storing universe_size and triples. This is a recommendation, not a failure.

Recommendations

• Create and link a [Rule] ThreeDimensionalMatching to ILP companion issue
• Clean up the example to present only the final revised instance
• Add a concrete complexity expression like 2^num_triples to the Complexity section
• Consider simplifying the schema by removing the redundant set_w, set_x, set_y fields

[isPANN]

Fix-issue changelog

• Example: Removed failed first attempts (two wrong matchings + "Let me redesign" text). Kept only the clean revised instance with unique matching {t0,t1,t2}. Added negative modification (remove t2 → NO).
• Schema: Simplified — removed redundant set_w/set_x/set_y fields (always {0..q-1}). Kept universe_size and triples only, matching ExactCoverBy3Sets pattern.
• Complexity: Added concrete expression "2^num_triples" for declare_variants!.
• Associated rules: Linked all rule issue numbers ([Rule] 3-DIMENSIONAL MATCHING to 3-MATROID INTERSECTION #386-[Rule] 3-Dimensional Matching to MinimumWeightDecoding #916).
• ILP: Added companion rule note.
• Schema notes: Added getter methods (universe_size(), num_triples()).
• Added Python validation script verifying positive (1/10) and negative (0/4) matchings.

Applied by /fix-issue.