[Rule] ThreeDimensionalMatching to ExactCoverBy3Sets

[isPANN]

Source

ThreeDimensionalMatching

Target

ExactCoverBy3Sets

Motivation

The tagged-disjoint-union construction exposes the direct equivalence between perfect 3-dimensional matching and exact cover by 3-sets. It adds a missing decision-to-decision connection between two canonical set problems with identity solution extraction.

Reference

Karp, “Reducibility Among Combinatorial Problems,” 1972; Garey and Johnson, Computers and Intractability, 1979, Appendix A (3-Dimensional Matching and Exact Cover by 3-Sets definitions). The direction below follows directly from the definitions.

Reduction Algorithm

Let the source contain three coordinate domains W=X=Y={0,...,q-1} and triples M=(t_0,...,t_{r-1}).

1. Create target universe {0,...,3q-1}, interpreted as the tagged disjoint union W union X union Y.
2. Map source triple (w,x,y) to target subset {w, q+x, 2q+y}.
3. Keep the configuration vector unchanged: selecting a target subset selects the corresponding source triple.

Every target subset has three distinct tagged elements even when w=x numerically. Selecting q pairwise disjoint target subsets covers all 3q elements iff the corresponding triples use every coordinate in each domain exactly once.

Size Overhead

Target metric	Formula
universe_size	3 * universe_size
num_subsets	num_triples
num_sets	num_triples

Validation Method

• Exhaust every family of triples for q=2 and compare witness configurations exactly.
• Test duplicate triples, empty q=0, unused coordinates, and triples with equal numeric coordinates across domains.
• Verify identity extraction and target tagging.

Example

1. Source instance: q=3, triples [(0,0,0),(1,1,1),(2,2,2),(0,1,2),(1,2,0)].
2. Construction: target universe {0,...,8} and subsets {0,3,6}, {1,4,7}, {2,5,8}, {0,4,8}, {1,5,6}.
3. Target instance: X3C with five candidate subsets and exact-cover size 3.
4. Round trip: selecting the first three subsets covers every target element exactly once and maps to the diagonal perfect matching. The two cross triples are mutually disjoint, but no available third triple covers the remaining tagged coordinates without overlap, so this partial matching cannot be extended to an exact cover.

BibTeX

@incollection{Karp1972,
  author = {Karp, Richard M.},
  title = {Reducibility Among Combinatorial Problems},
  booktitle = {Complexity of Computer Computations},
  pages = {85--103},
  publisher = {Springer},
  year = {1972},
  doi = {10.1007/978-1-4684-2001-2_9}
}

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	pred path ThreeDimensionalMatching ExactCoverBy3Sets --json reports no existing reduction path.
Non-trivial	✅ Pass	The construction changes a tripartite tuple instance into a 3-uniform set system by tagging all three coordinate domains; it is not a relabeling or subtype coercion.
Correctness	✅ Pass	The cited sources exist, their problem definitions match the repository models, and the tagged-union construction preserves every witness exactly.
Completeness	✅ Pass	The literature definitions cover the full source model, and the construction handles the traced empty, uncovered-coordinate, duplicate-triple, and equal-numeric-coordinate cases.
Well-written	⚠️ Warn	The worked target is correct, but its final explanation incorrectly says the two cross triples “create coordinate conflicts”; they are mutually coordinate-disjoint but cannot be extended by any available third triple.

Overall: 4 passed, 0 failed, 1 warning

---

Usefulness

Both endpoint names resolve with pred show. The source currently reduces to ThreeMatroidIntersection, MinimumWeightDecoding, ThreePartition, and ILP; no path to ExactCoverBy3Sets exists. This proposed edge therefore adds a novel connection rather than duplicating or being dominated by an existing composite path.

The motivation is substantive: the edge exposes the direct special-case relation and gives identity witness extraction.

Non-trivial

For each source triple (w,x,y), the algorithm constructs the target set {w,q+x,2q+y} over a new universe of size 3q. The offsets are essential structure: they turn three coordinate roles into disjoint target elements even when their numeric indices coincide. This is a direct construction, but not one of the skill's prohibited identity/subtype/one-variable-substitution cases.

Correctness

• Karp (1972): verified. The bibliographic record matches Richard M. Karp, Reducibility Among Combinatorial Problems, pp. 85–103, DOI 10.1007/978-1-4684-2001-2_9. In the primary text, the Main Theorem states, “All the problems on the following list are complete”; items 14 and 17 define Exact Cover and 3-Dimensional Matching, respectively. The 3DM property requires a matching of cardinality |T| whose elements do not agree in any coordinate (primary text, pp. 94–97). Karp's explicit nontrivial construction later in the paper is the opposite direction, Exact Cover → 3DM; this issue accurately says its own direction follows directly from the definitions rather than attributing this particular construction to that proof.
• Garey and Johnson (1979): verified. Appendix A3.1 lists 3DM as SP1 with three disjoint, equally sized domains and X3C as SP2 with a 3q-element universe and 3-element subsets. The SP2 entry explicitly records “Transformation from 3DM” (book scan). These are exactly the source and target domains used here.
• Independent semantic verification: the repository definitions agree with those sources. ThreeDimensionalMatching::evaluate accepts exactly q triples with distinct coordinates, while ExactCoverBy3Sets::evaluate accepts exactly q pairwise-disjoint 3-sets covering all 3q elements. After tagging, coordinate equality in a selected source family is equivalent to target-set intersection, so the configuration vector is preserved in both directions.
• Executable check: a brute-force script compared the complete witness vectors for all 256 families of triples over q=2; every source family and its tagged X3C image agreed. It also checked the issue's q=3 example exactly.

No lower-overhead construction is relevant here: any explicit target instance must output the r candidate subsets, and this construction uses exactly 3q universe elements and r subsets.

Completeness

Literature scope. Garey–Johnson SP1 allows every M ⊆ W × X × Y for disjoint sets W,X,Y of the same cardinality q; this matches the repository source model. SP2 accepts any collection of 3-element subsets over a universe of size 3q. The construction imposes no extra connectedness, occurrence, uniqueness, or non-emptiness precondition. Karp's definitions similarly quantify over arbitrary finite inputs. The proof is definitional: among q selected triples, distinctness in each of three size-q domains is equivalent to covering every tagged domain element exactly once.

Codebase scope. pred show ThreeDimensionalMatching --json reports source size fields num_triples and universe_size; the constructor permits q=0, missing coordinates, equal numeric values in different coordinates, and repeated triples in its Vec. It rejects only out-of-range coordinates. pred show ExactCoverBy3Sets --json confirms the target metrics universe_size, num_subsets, and num_sets, so all overhead-table names are valid. The target constructor permits an empty universe and repeated candidate subsets, and requires each individual subset to contain three distinct in-range elements; tagging guarantees that requirement.

Hand traces beyond the worked example:

1. Empty source: q=0, M=[] maps to universe size 0 and no subsets. Both models accept the empty configuration, so the YES instance is preserved.
2. Unused coordinate / NO instance: q=2, M=[(0,0,0),(0,1,1)] maps to {0,2,4} and {0,3,5} over {0,…,5}. The two sets overlap at tagged w=0 and tagged w=1 is uncovered. Neither source nor target has a feasible configuration.
3. Duplicate triples: two copies of (0,0,0) become two copies of {0,q,2q}. Selecting both repeats all three source coordinates and overlaps in the target; leaving one unselected preserves the original candidate identity. Duplicates therefore do not break witness extraction.
4. Equal numeric coordinates across domains: (1,1,1) maps to {1,q+1,2q+1}, whose three elements are distinct. Thus separate coordinate roles cannot collapse in the target.

Existing source rules (ThreeDimensionalMatching → ILP, → ThreeMatroidIntersection, and → MinimumWeightDecoding) also explicitly support q=0 or operate directly on all triples; the proposed mapping matches that source-domain coverage.

Well-written

All required sections are present and substantive. The steps are implementable, all symbols are introduced, extraction is explicit, and every overhead metric exists in the target schema. The example is non-degenerate and round-trip testable.

One sentence should be corrected: the sets for (0,1,2) and (1,2,0) are {0,4,8} and {1,5,6}, which are disjoint. They do not create a coordinate conflict with each other. The correct reason is that, after selecting both, none of the three remaining candidate triples can supply the uncovered tagged coordinates without overlapping a selected set.

Recommendations

• Replace “Selecting the two cross triples creates coordinate conflicts and cannot be extended” with: “The two cross triples are mutually disjoint, but no available third triple covers the remaining tagged coordinates without overlap, so this partial matching cannot be extended to an exact cover.”
• The num_subsets and num_sets overhead rows are both valid aliases in the current target schema; retaining both is acceptable, though one canonical metric would make the table more concise.

[isPANN]

Rule Fix

Diagnosis:

• Example correctness: the two cross triples are mutually coordinate-disjoint, so the original claim that they “create coordinate conflicts” was false. They instead fail because no available third triple completes the uncovered coordinates without overlap.
• All other structured checks passed: the reduction direction, both correctness directions, identity extraction, polynomial construction, overhead, Or -> Or type compatibility, and target-instance validity are sound. The undirected-rerouting check is not applicable to this set-system target.

Literature:

• Karp, “Reducibility Among Combinatorial Problems” (1972), defines Exact Cover and 3-Dimensional Matching but gives the nontrivial reduction in the opposite direction, Exact Cover to 3DM.
• Garey and Johnson, Computers and Intractability (1979), list 3DM and X3C consecutively as SP1 and SP2 and record X3C as obtained by transformation from 3DM. The issue’s tagged-disjoint-union construction is the direct special-case embedding supported by those definitions.

Changes:

• Corrected only the final worked-example explanation: the cross triples are disjoint but cannot be extended by any available third triple.

Smoke test:

• 127 checks passed across all mandatory buckets.
• Exact source/target witness-vector agreement held on 50 deterministic q=2 families.
• Confirmed the issue YES example, a concrete NO instance, empty q=0, singleton, duplicate triples, unused coordinates, equal numeric coordinates across domains, identity extraction, overhead formulas, and target validity.

[isPANN]

Issue Quality Check — Rule (Re-check)

Check	Result	Details
Usefulness	✅ Pass	pred path ThreeDimensionalMatching ExactCoverBy3Sets --json still reports no existing path.
Non-trivial	✅ Pass	Tagging the three coordinate roles constructs a 3-uniform set system and prevents numeric equality across roles from becoming target overlap.
Correctness	✅ Pass	The Karp and Garey–Johnson references are real and consistent with the repository models; independent smoke testing established exact witness preservation.
Completeness	✅ Pass	The mapping handles every repository-valid source instance, including empty universes, duplicate triples, unused coordinates, and equal numeric values in distinct coordinate roles.
Well-written	✅ Pass	The previously warned-about example sentence now correctly explains why the two cross triples cannot be extended. All required sections and valid target size metrics are present.

Overall: 5 passed, 0 failed, 0 warnings. Previously: 4 passed, 0 failed, 1 warning.

Verification notes

• Literature: Karp (1972) defines both problems and explicitly constructs Exact Cover → 3DM; Garey–Johnson (1979), Appendix A, lists 3DM as SP1 and X3C as SP2 with “Transformation from 3DM.” The proposed direction is the direct inclusion of perfect 3DM as X3C after tagging the three domains.
• Codebase: both endpoints resolve. ThreeDimensionalMatching permits q=0, repeated triples, unused coordinates, and equal numeric coordinates across roles; ExactCoverBy3Sets requires a universe divisible by three and three distinct in-range elements per subset. The offsets {w, q+x, 2q+y} satisfy those constraints for all valid source triples.
• Corner cases: the empty instance maps to empty X3C and remains YES; duplicate triples remain distinct candidates but cannot both be selected; an unused source coordinate remains an uncovered tagged target element and remains NO.
• Executable verification: 127 bucket checks passed, including exact witness agreement on 50 small instances, identity extraction, overhead spot-checks, and target validity.
• Example: {0,4,8} and {1,5,6} are mutually disjoint. The edited body now correctly states that none of the remaining three candidate subsets can cover the remaining tagged coordinates without overlap.