Reduction rule issues tiered implementation priority

[zazabap]

Summary

All 161 open [Rule] issues are categorized into tiers by readiness, Garey & Johnson (1979) reference confidence, and implementation difficulty. Each Tier 1 rule was independently verified by tracing a concrete example through the reduction (forward and backward directions).

Source: Garey & Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

Tier 1a — Simple (24 issues, both models exist, ~10 lines each)

Duality, restriction, or trivial embedding. All high confidence.

#	Source → Target	G&J Ref	Technique	Verified?
#387	Partition → SubsetSum	SP13	Target = S/2, same items	✅
#396	Partition → BinPacking	SR1	2 bins, cap = S/2	✅
#200	MinimumVertexCover → MinimumHittingSet	§3.2.1 p.64	Edges as 2-element sets	✅
#201	KClique → SubgraphIsomorphism	§3.2.1 p.64	Pattern = K_k	✅
#203	Partition → MultiprocessorScheduling	§3.2.1 p.65	m=2, D=S/2	✅
#199	HamiltonianCircuit → HamiltonianPath	ND20	Vertex dup + pendant	✅
#358	HamiltonianCircuit → LongestCircuit	ND28	Unit weights, K=|V|	✅
#259	HamiltonianCircuit → BottleneckTravelingSalesman	ND24	{1,2}-distance, B=1	✅
#234	HamiltonianPath → IsomorphicSpanningTree	ND8	HP = spanning tree ≅ P_n	✅
#241	PartitionIntoPathsOfLength2 → BoundedComponentSpanningForest	ND10	Same graph, unit weights	✅
#246	PartitionIntoTriangles → GraphPartitioning	ND14	K=3, J=|E|−|V|	✅
#379	MinimumDominatingSet → MinMaxMulticenter	ND50	Unit weights, B=1	✅
#380	MinimumDominatingSet → MinimumSumMulticenter	ND51	Unit weights, B=n−K	✅
#393	Partition → SumOfSquaresPartition	SP19	K=2, J=S²/2	✅
#424	RootedTreeArrangement → RootedTreeStorageAssignment	SR5	Edges → 2-element subsets	✅
#426	SubsetSum → CapacityAssignment	SR7	2 capacities, complementary cost/delay	✅
#434	OptimalLinearArrangement → ConsecutiveOnesMatrixAugmentation	SR16	Direct correspondence	✅
#463	KColoring(K3) → ConjunctiveQueryFoldability	SR30	Graph homomorphism to K₃	✅
#464	KClique → ConjunctiveBooleanQuery	SR31	k-clique as Boolean CQ	✅
#480	Partition → SequencingToMinimizeWeightedCompletionTime	SS13	weight=length, m=2	✅ (bound K formula incomplete in issue — correct formula: K = (Σsᵢ² + S²/2)/2)
#487	ExactCoverBy3Sets → StaffScheduling	SS20	1:1 schedule mapping	✅
#753	Satisfiability → NAESatisfiability	LO1	Add sentinel variable	✅
#238	HamiltonianCircuit → BoundedComponentSpanningForest	ND10	K=n−1, J=1	⚠️ Backward direction flawed: spanning path ≠ Hamiltonian circuit. Should be HP→BCSF or needs HC→HP gadget first
#381	ExactCoverBy3Sets → MaximumSetPacking	SP3	Same sets, k=|X|/3	⚠️ Stub — no reduction algorithm in issue body

22 verified, 2 need fixes before implementation.

Tier 1b — Moderate (33 issues, both models exist, ~30–80 lines)

High confidence (18 issues)

#	Source → Target	G&J Ref	Proof Source	Verified?
#197	KSatisfiability(K3) → MinimumVertexCover	Thm 3.3 pp.54–56	G&J main text	✅
#208	MinimumVertexCover → MinimumFeedbackArcSet	GT8	Karp 1972	✅
#229	KSatisfiability(K3) → KClique	GT19	Karp 1972; Sipser Thm 7.32	✅
#252	HamiltonianCircuit → BiconnectivityAugmentation	ND18	Eswaran & Tarjan 1976	✅
#254	HamiltonianCircuit → StrongConnectivityAugmentation	ND19	Eswaran & Tarjan 1976	✅
#261	HamiltonianCircuit → StackerCrane	ND26	Frederickson, Hecht & Kim 1978	✅
#262	HamiltonianCircuit → RuralPostman	ND27	Lenstra & Rinnooy Kan 1976	✅
#360	Partition → ShortestWeightConstrainedPath	ND30	Megiddo 1977	✅
#366	MaximumIndependentSet → IntegralFlowBundles	ND36	Sahni 1974	✅
#373	HamiltonianCircuit → QuadraticAssignment	ND43	Sahni & Gonzalez 1976	✅
#432	HamiltonianPath → ConsecutiveOnesSubmatrix	SR14	Booth 1975	✅
#205	Partition → SequencingWithinIntervals	Thm 3.8	G&J main text	✅
#166	KSatisfiability → MaxCut	§3.2.5	GJ&Stockmeyer 1976	⚠️ Threshold formula n·m+2m inconsistent with described construction; needs rederivation
#277	DirectedTwoCommodityIntegralFlow → UndirectedTwoCommodityIntegralFlow	ND39	Even, Itai & Shamir 1976	⚠️ Empty issue body
#363	Partition → IntegralFlowWithMultipliers	ND33	Sahni 1974	⚠️ Flow ≥ R is weaker than exact partition; counterexample A={1,3}
#459	MinimumVertexCover → MinimumCardinalityKey	SR26	Lucchesi & Osborne 1977	⚠️ FDs don't allow deriving non-selected vertex attrs; key closure fails
#523	KClique → PartiallyOrderedKnapsack	MP12	Ibarra & Kim 1975	⚠️ Reverse direction fails; counterexample C₅ with J=3 has no 3-clique but POK is feasible
#472	OptimalLinearArrangement → SequencingToMinimizeWeightedCompletionTime	SS4	Lawler 1978	⚠️ Bound K=K_OLA+C undefined; no formula for C

12 verified, 6 need fixes.

Medium confidence (15 issues)

#	Source → Target	G&J Ref	Proof Source	Verified?
#109	LongestCommonSubsequence → MaximumIndependentSet	—	Apostolico & Guerra 1987	✅
#204	MinimumVertexCover → EnsembleComputation	PO9	G&J appendix	✅
#231	KClique → BalancedCompleteBipartiteSubgraph	GT24	Johnson 1987	✅
#425	MinimumVertexCover → MultipleCopyFileAllocation	SR6	Van Sickle & Chandy 1977	✅
#437	KColoring(K3) → TwoDimensionalConsecutiveSets	SR19	Lipsky 1977	✅
#649	PaintShop → QUBO	—	Streif et al. 2021	✅
#385	MinimumVertexCover → ComparativeContainment	SP10	Plaisted 1976	⚠️ Containment direction wrong — Y⊆Rᵢ is backwards from VC intersection requirement
#423	Partition → ExpectedRetrievalCost	SR4	Cody & Coffman 1976	⚠️ m=2 case degenerate (zero latency); should be 3-Partition source
#460	MinimumHittingSet → AdditionalKey	SR27	Beeri & Bernstein 1978	⚠️ FDs broken — universe attrs can't determine each other
#462	MinimumHittingSet → BoyceCoddNormalFormViolation	SR29	Beeri & Bernstein 1978	⚠️ FDs only produce auxiliary attrs; no BCNF violation possible
#250	MinimumVertexCover → MinimumCutIntoBoundedSets	ND17	GJ&Stockmeyer 1976	⚠️ Vague — admits intermediate chain through Simple Max Cut; example self-contradictory
#435	HamiltonianPath → ConsecutiveBlockMinimization	SR17	Kou 1977	⚠️ Multiple constructions attempted, all fail on non-trivial examples
#436	HamiltonianPath → ConsecutiveSets	SR18	Kou 1977	⚠️ Same problem as #435 — correct Kou construction not reproduced
#461	MinimumCardinalityKey → PrimeAttributeName	SR28	Lucchesi & Osborne 1977	⚠️ Construction incomplete — placeholder text, missing FDs
#206	KClique → MinimumTardinessSequencing	Thm 3.10	G&J main text	⏸️ On hold: decision/optimization mismatch

6 verified, 8 need fixes, 1 on hold.

Tier 1c — Complex (24 issues, both models exist, 80+ lines)

Not individually verified (complex gadgets require original papers). Grouped by confidence.

High confidence (5)

#	Source → Target	G&J Ref	Proof Source
#198	MinimumVertexCover → HamiltonianCircuit	Thm 3.4 pp.56–60	G&J main text, full proof
#368	KSatisfiability(K3) → DirectedTwoCommodityIntegralFlow	ND38	Even, Itai & Shamir 1976
#370	KSatisfiability(K3) → DisjointConnectingPaths	ND40	Knuth/Karp/Lynch 1974–75
#476	KSatisfiability(K3) → PrecedenceConstrainedScheduling	SS9	Ullman 1975
#582	QuantifiedBooleanFormulas → GeneralizedHex	GP1	Even & Tarjan 1976 (PSPACE)

Medium confidence (11)

#	Source → Target	G&J Ref	Proof Source
#260	KSatisfiability(K3) → MixedChinesePostman	ND25	Papadimitriou 1976 (JACM)
#364	KSatisfiability(K3) → PathConstrainedNetworkFlow	ND34	Promel 1978
#365	KSatisfiability(K3) → IntegralFlowHomologousArcs	ND35	Sahni 1974
#367	Satisfiability → UndirectedFlowLowerBounds	ND37	Itai 1977
#371	KSatisfiability(K3) → LengthBoundedDisjointPaths	ND41	Itai, Perl & Shiloach 1977
#427	MinimumVertexCover → ShortestCommonSupersequence	SR8	Maier 1978
#428	MinimumVertexCover (cubic) → ShortestCommonSupersequence	SR9	Gallant, Maier & Storer 1980
#429	MinimumVertexCover → LongestCommonSubsequence	SR10	Maier 1978
#478	MinimumVertexCover → SchedulingWithIndividualDeadlines	SS11	Brucker, Garey & Johnson 1977
#486	KSatisfiability(K3) → TimetableDesign	SS19	Even, Itai & Shamir 1976
#732	Satisfiability → IntegralFlowHomologousArcs	ND35	Sahni 1974

Low confidence (8)

#	Source → Target	G&J Ref	Issue
#243	KSatisfiability(K3) → MultipleChoiceBranching	ND11	Unpublished G&J — vague sketch
#247	KSatisfiability(K3) → AcyclicPartition	ND15	Unpublished G&J — vague
#374	MinimumVertexCover → MinimumDummyActivitiesPert	ND44	Krishnamoorthy & Deo 1977 (tech report)
#383	MinimumVertexCover → SetBasis	SP7	Stockmeyer 1975 (IBM report)
#431	KColoring(K3) → SparseMatrixCompression	SR13	Even et al. 1977 (unpublished ms)
#453	MinimumSetCovering → StringToStringCorrection	SR20	Wagner 1975 (short conf paper)
#454	PartialFeedbackEdgeSet → GroupingBySwapping	SR21	Howell 1977 — no construction
#458	KSatisfiability(K3) → RectilinearPictureCompression	SR25	Masek 1978 (unpublished MIT ms)
#468	KSatisfiability(K3) → ConsistencyOfDatabaseFrequencyTables	SR35	Reiss 1977 (stats dept report)

Special Flags

#	Issue	Flag
#236	HamiltonianPath → KthBestSpanningTree	Turing reduction — cannot implement as ReduceTo<T>
#369	D2CIF → U2CIF	Duplicate of #277

Tier 2 — Already Implemented (2 issues)

#	Source → Target	File
#733	IntegralFlowHomologousArcs → ILP	integralflowhomologousarcs_ilp.rs
#728	TimetableDesign → ILP	timetabledesign_ilp.rs

These should be closed.

Tier 3 — Needs New Model(s) (75 issues)

All cite explicit G&J references (overwhelmingly high confidence). Grouped by missing model.

Key missing source models

Missing Model	G&J Code	Issues Blocked
ThreePartition	SP15	#376, #375, #389, #397, #469, #473, #477, #482, #485 (9)
ThreeDimensionalMatching	SP1	#378, #386, #390, #391, #398 (5)

Target missing — source exists (56 issues)

QBF → PSPACE games (7)

#	Target (missing)	G&J Ref
#583	GeneralizedGeography	GP2
#584	GeneralizedKayles	GP3
#585	SequentialTruthAssignment	GP4
#586	VariablePartitionTruthAssignment	GP5
#587	Sift	GP6
#588	AlternatingHittingSet	GP7
#589	AlternatingMaximumWeightedMatching	GP8

3SAT → Algebra/Number theory (15)

#	Target (missing)	G&J Ref
#553	QuadraticCongruences	AN1
#554	SimultaneousIncongruences	AN2
#556	ComparativeDivisibility	AN4
#557	ExponentialExpressionDivisibility	AN5
#558	NonDivisibilityOfAProductPolynomial	AN6
#559	NonTrivialGreatestCommonDivisor	AN7
#560	QuadraticDiophantineEquations	AN8
#561	RootOfModulus1	AN9
#562	NumberOfRootsForAProductPolynomial	AN10
#563	PeriodicSolutionRecurrenceRelation	AN11
#564	PermanentEvaluation	AN12
#566	EquilibriumPoint	AN14
#567	UnificationWithCommutativeOperators	AN15
#568	UnificationForFinitelyPresentedAlgebras	AN16
#569	IntegerExpressionMembership (SubsetSum)	AN17

Scheduling targets (7)

#	Source	Target (missing)	G&J Ref
#470	KClique	SequencingToMinimizeTardyTasks	SS1
#471	Partition	SequencingToMinimizeTardyTaskWeight	SS2
#474	Partition	SequencingWithDeadlinesAndSetUpTimes	SS3
#479	KSatisfiability(K3)	PreemptiveScheduling	SS10
#481	Partition	OpenShopScheduling	SS14
#488	Partition	ProductionPlanning	SS17
#489	KSatisfiability(K3)	DeadlockAvoidance	SS18

Math programming targets (7)

#	Source	Target (missing)	G&J Ref
#517	Partition	QuadraticProgramming	MP1
#518	KSatisfiability(K3)	CostParametricLinearProgramming	MP2
#519	HamiltonianCircuit	FeasibleBasisExtension	MP3
#520	HamiltonianCircuit	TSP PolytopeNonAdjacency	MP4
#521	SubsetSum	IntegerKnapsack	MP5
#522	Partition	ContinuousMultipleChoiceKnapsack	MP6
#524	ComparativeContainment	ComparativeVectorInequalities	MP8

Network/graph targets (7)

#	Source	Target (missing)	G&J Ref
#256	SteinerTreeInGraphs	NetworkReliability	ND20
#257	MinimumVertexCover	NetworkSurvivability	ND21
#361	HamiltonianPath	KthShortestPath	ND31 (Turing)
#362	ExactCoverBy3Sets	MinimumEdgeCostFlow	ND32
#372	KSatisfiability(K3)	MaxFixedLengthDisjointPaths	ND42
#590	MinimumVertexCover	Annihilation	GP9
#591	MinimumSetCovering	LR Hackenbush	GP10

Sets/partitions targets (6)

#	Source	Target (missing)	G&J Ref
#382	NAESatisfiability	SetSplitting	SP4
#384	KColoring(K3)	IntersectionPattern	SP9
#388	ExactCoverBy3Sets	SubsetProduct	SP14
#392	ExactCoverBy3Sets	ExpectedComponentSum	SP18
#394	SubsetSum	KthLargestSubset	SP20
#395	Partition	KthLargestMTuple	SP21

Storage/retrieval targets (7)

#	Source	Target (missing)	G&J Ref
#430	KSatisfiability(K3)	HittingString	SR12
#433	HamiltonianPath (cubic)	ConsecutiveOnesMatrixPartition	SR15
#455	MinimumVertexCover	MinExternalMacroDataCompression	SR11
#456	MinimumVertexCover	InternalMacroDataCompression	SR11
#457	ExactCoverBy3Sets	RegularExpressionSubstitution	SR11
#465	KSatisfiability(K3)	TableauEquivalence	SR33
#467	MinimumHittingSet	SafetyOfDBTransactionSystems	SR34

Source missing, target exists (6)

#	Source (missing)	Target	G&J Ref
#359	HamiltonianPathBetweenTwoVertices	LongestPath	ND29
#469	ThreePartition	SequencingWithReleaseTimesAndDeadlines	SS7
#473	ThreePartition	SequencingToMinimizeWeightedTardiness	SS6
#475	RegisterSufficiency	SeqMinMaxCumulativeCost	SS5
#477	ThreePartition	ResourceConstrainedScheduling	SS9
#482	ThreePartition	FlowShopScheduling	SS15

Both missing (13)

#	Source (missing)	Target (missing)	G&J Ref
#375	ThreePartition	IntersectionGraphForSegmentsOnAGrid	ND46
#376	ThreePartition	EdgeEmbeddingOnAGrid	ND47
#377	Planar3SAT	GeometricConnectedDominatingSet	ND48
#378	ThreeDimensionalMatching	MinimumBroadcastTime	ND49
#386	ThreeDimensionalMatching	ThreeMatroidIntersection	SP11
#389	ThreeDimensionalMatching	ThreePartition	SP15
#390	ThreeDimensionalMatching	Numerical3DMatching	SP16
#391	Numerical3DMatching	NumericalMatchingWithTargetSums	SP17
#397	ThreePartition	DynamicStorageAllocation	SR2
#398	ThreeDimensionalMatching	PrunedTrieSpaceMinimization	SR3
#466	Monotone3SAT	SerializabilityOfDBHistories	SR33
#485	ThreePartition	JobShopScheduling	SS14
#555	QuadraticDiophantineEquations	SimultaneousDivisibility	AN3

Implementation Priority

Priority	Description	Count
🟢 Implement first	Tier 1a ✅ verified	22
🟡 Implement second	Tier 1b high-confidence ✅ verified	12
🟠 Implement third	Tier 1b medium-confidence ✅ verified	6
🔵 Fix first, then implement	Tier 1a/1b ⚠️ needing correction	16
⚪ Implement when ready	Tier 1c (complex gadgets, not individually verified)	24
⏳ Blocked on new models	Tier 3	75
✔️ Close	Tier 2 (already implemented) + #369 (duplicate)	3
❓ Special	#236 (Turing reduction)	1

Redundancy Note

Before implementing any Tier 1 rule, run topology-sanity-check redundancy <source> <target> to verify it is not dominated by an existing path.

[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.