Reduction rule issues tiered implementation priority

[zazabap]

Dashboard

Updated 2026-04-02 after batch /verify-reduction run on 52 issues (PR #992).
Source: Garey & Johnson, Computers and Intractability, 1979.
Catalog: 188 types, 201 reductions. NP-hardness chain: 29 types reachable from 3-SAT.

/verify-reduction batch results (51 issues processed): 34 verified & implementable, 5 math-correct but type-incompatible, 8 refuted, 3 blocked on papers, 1 stopped at type gate.

Category	Count
Implemented (closed)	65
Ready to implement	34
Needs work	28
Not yet verified	19
Waiting on models	~16
Close	20

---

1. Ready to implement (34)

Verified by /verify-reduction (PR #992). Each has Typst proof + constructor + adversary Python + test vectors. Use /add-reduction to implement.

#	Source → Target	Checks	Reference
#973	SubsetSum → Partition	644K
#382	NAESatisfiability → SetSplitting	97K
#844	KColoring → PartitionIntoCliques	48K	complement duality
#379	MinDomSet → MinMaxMulticenter	241K	identity
#380	MinDomSet → MinSumMulticenter	3.0M	identity
#471	Partition → SeqMinTardyTaskWeight	111K
#862	3SAT → OneInThreeSatisfiability	12K	Schaefer 1978
#359	HamPathBetween2 → LongestPath	313K	identity, K=n-1
#481	Partition → OpenShopScheduling	137K	Gonzalez & Sahni 1976
#859	X3C → AlgebraicEquationsOverGF2	281K
#868	Satisfiability → NonTautology	435M	De Morgan negation
#845	NAE-SAT → PartIntoPerfMatchings	18K	K4 gadgets
#860	X3C → MinWeightSolnLinearEquations	180K	incidence matrix
#842	SetSplitting → Betweenness	183K	Opatrny 1979
#911	HamPath → DegreeConstrSpanningTree	23K	identity, K=2
#889	PartIntoCliques → MinCoverByCliques	49K	forward-only
#882	3SAT → Kernel	274K	Chvátal 1973
#893	MVC → MinMaximalMatching	15K	same graph
#918	3SAT → CyclicOrdering	16K	Galil & Megiddo 1977
#884	3SAT → MonochromaticTriangle	12K	padded intermediates
#388	X3C → SubsetProduct	333K	prime encoding
#569	SubsetSum → IntegerExprMembership	739K	Stockmeyer-Meyer 1973
#488	Partition → ProductionPlanning	103K	corrected Lenstra et al.
#521	SubsetSum → IntegerKnapsack	66K	one-way
#389	3DM → ThreePartition	48K	GJ 1975 chain
#397	ThreePartition → DynamicStorageAlloc	23K	bin-packing
#554	3SAT → SimultaneousIncongruences	12K	CRT encoding
#872	3SAT → RegisterSufficiency	11K	Sethi 1975
#368	3SAT → Dir2CommodityIntegralFlow	128K	Even-Itai-Shamir 1976
#479	3SAT → PreemptiveScheduling	11K	Ullman 1975
#553	3SAT → QuadraticCongruences	76K	Manders-Adleman 1978
#905	3SAT → FeasibleRegisterAssignment	11K	chain gadgets
#377	Planar3SAT → MinGeometricConnDomSet	13K	geometric embedding
#476	3SAT → PrecedenceConstrScheduling	367	Ullman 1975 (P4→P2)

---

2. Needs work (28)

Type-incompatible — needs decision variants (PR #996) (6)

5 of 6 were run through /verify-reduction and confirmed mathematically correct (*), but the codebase Value types are incompatible for ReduceTo. #892 was stopped at the type gate without mathematical verification.

#	Source(Type) → Target(Type)	Mismatch	Resolution
#198 *	MVC(Min) → HamiltonianCircuit(Or)	Min→Or	Needs VertexCover(Or)
#892	MVC(Min) → HamiltonianPath(Or)	Min→Or	Needs VertexCover(Or)
#894 *	MVC(Min) → PartialFeedbackEdgeSet(Or)	Min→Or	Needs VertexCover(Or)
#890 *	MaxCut(Max) → OLA(Min)	Max→Min	Needs decision variant
#888 *	OLA(Min) → RootedTreeArrangement(Or)	Min→Or	Needs decision variant
#395 *	Partition(Or) → KthLargestMTuple(Sum)	Or→Sum	Turing; needs ReduceToAggregate

Blocked on original papers (3)

* = ran through /verify-reduction, could not reconstruct correct algorithm.

#	Source → Target	Paper needed
#474 *	Partition → SeqDeadlinesSetUpTimes	Bruno & Downey 1978
#390 *	3DM → Numerical3DM	No direct reduction; chain through 4-Partition
#912	HamiltonianPath → IsomorphicSpanningTree	Likely duplicate of #234

Needs fix — known defects in issue description (19)

Not yet run through /verify-reduction.

#	Source → Target	Defect
#166	KSatisfiability → MaxCut	Threshold formula inconsistent
#277	Dir2CommodityFlow → Undir2CommodityFlow	Empty body
#363	Partition → IntegralFlowWithMultipliers	Counterexample
#459	MVC → MinimumCardinalityKey	FDs wrong
#523	KClique → PartiallyOrderedKnapsack	Reverse direction fails
#472	OLA → SeqMinWeightedCompletion	Bound K undefined
#385	MVC → ComparativeContainment	Direction backwards
#423	Partition → ExpectedRetrievalCost	Degenerate
#460	MinimumHittingSet → AdditionalKey	FDs broken
#462	MinimumHittingSet → BoyceCoddNormalFormViolation	FDs broken
#250	MVC → MinimumCutIntoBoundedSets	Self-contradictory
#435	HamiltonianPath → ConsecutiveBlockMinimization	Construction fails
#436	HamiltonianPath → ConsecutiveSets	Same as #435
#461	MinimumCardinalityKey → PrimeAttributeName	Incomplete
#425	MVC → MultipleCopyFileAllocation	Needs cleanup
#206	KClique → MinimumTardinessSequencing	Decision/optimization mismatch
#434	OLA → ConsecutiveOnesMatrixAugmentation	Decision/optimization mismatch
#463	KColoring(K3) → ConjunctiveQueryFoldability	Set-equality semantics
#238	HamiltonianCircuit → BoundedComponentSpanningForest	Direction flawed

---

3. Not yet verified (19)

Both models exist; issue has a construction but not yet run through /verify-reduction.

Medium confidence (10)

#	Source → Target	G&J Ref
#260	KSatisfiability(K3) → MixedChinesePostman	ND25
#364	KSatisfiability(K3) → PathConstrainedNetworkFlow	ND34
#365	KSatisfiability(K3) → IntegralFlowHomologousArcs	ND35
#367	Satisfiability → UndirectedFlowLowerBounds	ND37
#371	KSatisfiability(K3) → LengthBoundedDisjointPaths	ND41
#427	MVC → ShortestCommonSupersequence	SR8
#429	MVC → LongestCommonSubsequence	SR10
#478	MVC → SchedulingWithIndividualDeadlines	SS11
#486	KSatisfiability(K3) → TimetableDesign	SS19
#732	Satisfiability → IntegralFlowHomologousArcs	ND35

Low confidence (9)

#	Source → Target	G&J Ref
#243	KSatisfiability(K3) → MultipleChoiceBranching	ND11
#247	KSatisfiability(K3) → AcyclicPartition	ND15
#374	MVC → MinimumDummyActivitiesPert	ND44
#383	MVC → SetBasis	SP7
#431	KColoring(K3) → SparseMatrixCompression	SR13
#453	MinimumSetCovering → StringToStringCorrection	SR20
#454	PartialFeedbackEdgeSet → GroupingBySwapping	SR21
#458	KSatisfiability(K3) → RectilinearPictureCompression	SR25
#468	KSatisfiability(K3) → ConsistencyOfDatabaseFrequencyTables	SR35

---

4. Waiting on models (~16 issues)

At least one model missing. Major blockers: NoWaitFlowShop (#483), TwoProcessorFlowShop (#484), NetworkReliability, DirectedHamiltonianCircuit, Monotone3SAT, PermutationGeneration (#874), various DB/misc (~10 more).

---

5. Close (20)

Refuted by /verify-reduction — incorrect issue construction (8)

#	Source → Target	Failure
#846	MinMaximalMatching → MaxAchromaticNumber	50 counterexamples
#843	KColoring(K3) → PartitionIntoForests	K4 counterexample
#847	MinMaximalMatching → MinMatrixDomination	P3 counterexample
#822	X3C → AcyclicPartition	959 counterexamples
#913	X3C → BoundedDiameterSpanningTree	relay attack
#370	3SAT → DisjointConnectingPaths	trivial clause paths
#920	3SAT → NonLivenessFreePetriNet	direction error
#475	RegSufficiency → SeqMinMaxCumulativeCost	36.3% mismatch

Duplicates — close the "New" column (9)

Close	Keep	Rule
#828	#397	ThreePartition → DynamicStorageAllocation
#827	#391	N3DM → NumericalMatchingWithTargetSums
#826	#390	3DM → Numerical3DM
#824	#389	3DM → ThreePartition
#858	#388	X3C → SubsetProduct
#857	#386	3DM → ThreeMatroidIntersection
#891	#198	MVC → HamiltonianCircuit
#841	#382	NAE-SAT → SetSplitting
#369	#277	Dir2CommodityFlow → Undir2CommodityFlow

Turing reductions — cannot implement as ReduceTo (2)

#236, #361

---

Implemented rules (65 closed)

PR #972 (10): #396, #469, #473, #477, #482, #485, #769, #821, #823, #849
PR #976 (12 ILP): #961–#971 + MinimumGraphBandwidth→ILP, NumericalMatchingWithTargetSums→ILP
Legacy (43): See closed [Rule] issues.

[GiggleLiu]

Note: topology-sanity-check redundancy <source> <target> only tells potential risk of redundant rule. Even if the check fails, the new rule may still provide some advantage. So, additional check on the potentially redudant rule is nessesary.

[isPANN]

Please kindly check the following items (PR #804):

• Paper (PDF): check definition, proof sketch, example figure, and reproducible pred commands for all 11 reduction rules
• Implementation (Optional): spot-check the source files changed in this PR for correctness

💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.