[Contribution] 10 Reduction Rules

[zazabap]

Contribution Summary

Per the contribution guidelines, I am submitting 10 non-trivial reduction rules for authorship consideration.

Problem Models Filed (4)

Issue	Problem	Category
#108	LongestCommonSubsequence	String/Sequence
#114	Knapsack	Optimization
#117	GraphPartitioning	Graph
#122	SteinerTree	Network Design

Reduction Rules Filed (10)

Issue	Source → Target	Domain Crossing
#109	LCS → MaximumIndependentSet	String → Graph
#110	LCS → ILP	String → Algebraic
#126	KSatisfiability → SubsetSum	Formula → Number Theory
#116	Knapsack → QUBO	Optimization → Algebraic
#125	Knapsack → ClosestVectorProblem	Optimization → Lattice Theory
#118	GraphPartitioning → ILP	Graph → Algebraic
#119	GraphPartitioning → QUBO	Graph → Algebraic
#120	GraphPartitioning → MaxCut	Graph → Graph (constrained → unconstrained)
#121	GraphPartitioning → SpinGlass	Graph → Physics
#123	SteinerTree → ILP	Network → Algebraic

Highlights

• Cross-domain reductions: KSatisfiability → SubsetSum (Karp's original, S-tier) and Knapsack → CVP (Lagarias-Odlyzko, S-tier) bridge fundamentally different mathematical domains
• New graph topology: GraphPartitioning → MaxCut creates a new path into the MaxCut node; SubsetSum gets its first incoming edge
• Industrial relevance: GraphPartitioning (VLSI, parallel computing), SteinerTree (network design), Knapsack (resource allocation)

[zazabap]

Reduction Rule Tier Assessment

Tier ranking of all reduction rules — both implemented in the codebase and filed as issues — based on non-triviality, theoretical significance, and cross-domain value.

Tier S — Foundational, Textbook-Defining Reductions

Rule	Status	Rationale
SAT → 3-Coloring	Implemented	Classic Karp reduction. OR-gadget + TRUE/FALSE/AUX triangle. Every complexity textbook.
SAT → MaximumIndependentSet	Implemented	Karp classic. Clause-clique + complementary-literal edges. Canonical NP-completeness proof for MaxIS.
Factoring → CircuitSAT	Implemented	Array multiplier circuit. Bridges number theory → boolean logic. RSA security foundation.
CircuitSAT → SpinGlass	Implemented	Logic-gate Ising gadgets (AND/OR/XOR/NOT). Bridges CS → physics. Each gadget carefully verified.
ILP → QUBO	Implemented	General-purpose. Slack binary encoding + penalty method. Workhorse of the repo.
#126 KSatisfiability → SubsetSum	Filed	Karp-original. Base-10 digit encoding, formula → number theory. Canonical proof SubsetSum is NP-complete.
#125 Knapsack → CVP	Filed	Lagarias-Odlyzko (1985). Broke Merkle-Hellman cryptosystem. Discrete optimization → lattice theory.

Tier A — Important Cross-Domain or Non-Trivial

Rule	Status	Rationale
SpinGlass ↔ MaxCut	Implemented	Bidirectional. Ancilla vertex trick for onsite terms is elegant.
SAT → MinDominatingSet	Implemented	Gadget-based, connects SAT to different graph family.
MinVertexCover → MinSetCovering	Implemented	Graph covering → set covering abstraction lift.
#120 GraphPartitioning → MaxCut	Filed	Penalty-weighted graph completion. Encodes balance constraint into unconstrained objective.
#109 LCS → MaximumIndependentSet	Filed	Match-graph construction. String → graph category crossing. Proves multi-string LCS hardness.

Tier B+ — Solid, Non-Trivial Formulations

Rule	Status	Rationale
kSAT → QUBO	Implemented	Direct clause-to-penalty mapping. Important for quantum pipeline.
Coloring → ILP	Implemented	Assignment variables + conflict constraints.
TSP → ILP	Implemented	Subtour elimination formulation. Standard operations research.
#121 GraphPartitioning → SpinGlass	Filed	Ising model mapping. Connects combinatorial optimization → statistical physics.
#123 SteinerTree → ILP	Filed	Multicommodity flow formulation. Standard exact method for VLSI routing.

Tier B — Standard but Useful

Rule	Status	Rationale
MaxIS → QUBO	Implemented	Standard penalty formulation for quantum computing.
MaxIS → MaxSetPacking	Implemented	Direct type embedding.
MaxMatching → ILP	Implemented	Degree constraints on edge variables.
MaxSetPacking → ILP, QUBO	Implemented	Standard formulations.
MinDomSet → ILP	Implemented	Standard ILP encoding.
MinSetCovering → ILP	Implemented	Standard ILP encoding.
MinVertexCover → ILP, QUBO	Implemented	Standard formulations.
MaxClique → ILP	Implemented	Standard ILP encoding.
Coloring → QUBO	Implemented	Standard penalty formulation.
MaxMatching → MaxSetPacking	Implemented	Type embedding.
#91 CVP → QUBO	Filed (other)	Standard QUBO encoding.
#97 BinPacking → ILP	Filed (other)	Assignment + capacity constraints.
#116 Knapsack → QUBO	Filed	Slack-variable binary expansion + penalty. Standard quantum encoding.
#119 GraphPartitioning → QUBO	Filed	Balance constraint penalty encoding.
#118 GraphPartitioning → ILP	Filed	Partition + edge-crossing variables.
#110 LCS → ILP	Filed	Match-pair variables with ordering constraints.

Tier C — Near-Trivial / Identity Mappings

Rule	Status	Rationale
MinVertexCover ↔ MaxIS	Implemented	Complement: flip 0↔1. Same graph. Simplest possible reduction.
SAT → kSAT	Implemented	Clause splitting with auxiliary variables. Mechanical.
QUBO ↔ ILP	Implemented	Direct variable/constraint mapping.
Various _casts rules	Implemented	Type-level variant conversions. Identity mappings.

---

Summary: 10 filed rules include 2 S-tier (matching the repo's best), 2 A-tier, 2 B+-tier, and 4 B-tier.