Reduction rule issues tiered implementation priority

[zazabap]

Summary

Updated 2026-03-31 after PR #972 merged (10 reduction rules). Cross-referenced all open [Rule] issues against the current model inventory (pred list: 163 types, 189 reductions).

Source: Garey & Johnson, Computers and Intractability, 1979.

NP-hardness proof chain (reachable from 3-SAT): 29 problem types (up from 28; +MinimumCutIntoBoundedSets via PR #972).

Stats:

• Implemented: 53 rules closed since original triage (43 legacy + 10 from PR feat: add 10 reduction rules (#770) #972)
• Ready (both models exist): ~94 open issues (103 prior − 10 implemented + 1 new [Rule] SUBSET SUM to PARTITION #973)
• Blocked (needs new model): ~52 open issues
• Should close: 3 issues ([Rule] IntegralFlowHomologousArcs → ILP #733, [Rule] TimetableDesign to ILP #728 already implemented; [Rule] DIRECTED TWO-COMMODITY INTEGRAL FLOW to UNDIRECTED TWO-COMMODITY INTEGRAL FLOW #369 duplicate of [Rule] DIRECTED TWO-COMMODITY INTEGRAL FLOW to UNDIRECTED TWO-COMMODITY INTEGRAL FLOW #277)
• Potential duplicates: 6 pairs to resolve ([Rule] EXACT COVER BY 3-SETS to SET PACKING #823 resolved as dup, implemented via PR feat: add 10 reduction rules (#770) #972)

Highest-leverage missing reductions:

• [Rule] SUBSET SUM to PARTITION #973 SubsetSum → Partition (NEW) — would unlock ~12 problems including Knapsack, BinPacking, ThreePartition scheduling chain
• [Rule] VERTEX COVER to HAMILTONIAN CIRCUIT #198 MinimumVertexCover → HamiltonianCircuit — would unlock ~9 problems including TSP, scheduling, augmentation

---

Tier 1a — Simple (both models exist, duality/restriction/trivial)

Ready (4)

#	Source → Target	G&J Ref	Notes
#379	MinimumDominatingSet → MinMaxMulticenter	ND50	Verify K param
#380	MinimumDominatingSet → MinimumSumMulticenter	ND51	Same K issue
#888	OptimalLinearArrangement → RootedTreeArrangement	—
#822	ExactCoverBy3Sets → AcyclicPartition	—

Implemented by PR #972 (1)

#	Source → Target	G&J Ref
#396	Partition → BinPacking	SR1

Needs fix (1)

#	Source → Target	Notes
#238	HamiltonianCircuit → BoundedComponentSpanningForest	Direction flawed

Design decision needed (3)

#	Source → Target	Notes
#434	OptimalLinearArrangement → ConsecutiveOnesMatrixAugmentation	Decision/optimization mismatch
#463	KColoring(K3) → ConjunctiveQueryFoldability	Set-equality semantics
#912	HamiltonianPath → IsomorphicSpanningTree	Likely duplicate of closed #234

---

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

Ready (10 + 35 newly unblocked)

Previously ready (4 remaining):

#	Source → Target	G&J Ref
#892	MinimumVertexCover → HamiltonianPath	—
#894	MinimumVertexCover → PartialFeedbackEdgeSet	—
#890	MaxCut → OptimalLinearArrangement	—
#973	SubsetSum → Partition	SP12–SP13 (NEW)

ILP/variant rules (1 remaining):

#	Source → Target
#783	SchedulingToMinimizeWeightedCompletionTime → ILP

Implemented by PR #972 (9):

#	Source → Target	G&J Ref
#821	NAESatisfiability → MaxCut	—
#849	MaxCut → MinimumCutIntoBoundedSets	—
#469	ThreePartition → SequencingWithReleaseTimesAndDeadlines	SS7
#473	ThreePartition → SequencingToMinimizeWeightedTardiness	SS6
#477	ThreePartition → ResourceConstrainedScheduling	SS9
#482	ThreePartition → FlowShopScheduling	SS15
#485	ThreePartition → JobShopScheduling	SS14
#769	ILP/i32 → ILP/bool	—
#823	ExactCoverBy3Sets → MaximumSetPacking	—

Newly unblocked by PR #960 (24 Tier 1b):

#	Source → Target	Unblocked by
#359	HamiltonianPathBetweenTwoVertices → LongestPath	HamiltonianPathBetweenTwoVertices
#382	NAESatisfiability → SetSplitting	SetSplitting
#388	ExactCoverBy3Sets → SubsetProduct	SubsetProduct (dup #858)
#389	ThreeDimensionalMatching → ThreePartition	ThreeDimensionalMatching (dup #824)
#390	ThreeDimensionalMatching → Numerical3DimensionalMatching	ThreeDimensionalMatching (dup #826)
#397	ThreePartition → DynamicStorageAllocation	DynamicStorageAllocation (dup #828)
#471	Partition → SequencingToMinimizeTardyTaskWeight	SequencingToMinimizeTardyTaskWeight
#474	Partition → SequencingWithDeadlinesAndSetUpTimes	SequencingWithDeadlinesAndSetUpTimes
#481	Partition → OpenShopScheduling	OpenShopScheduling
#841	NAESatisfiability → SetSplitting	SetSplitting (dup #382)
#842	SetSplitting → Betweenness	SetSplitting + Betweenness
#843	KColoring(K3) → PartitionIntoForests	PartitionIntoForests
#844	KColoring → PartitionIntoCliques	PartitionIntoCliques
#845	NAESatisfiability → PartitionIntoPerfectMatchings	PartitionIntoPerfectMatchings
#846	MinimumMaximalMatching → MaximumAchromaticNumber	MinimumMaximalMatching + MaximumAchromaticNumber
#847	MinimumMaximalMatching → MinimumMatrixDomination	MinimumMaximalMatching + MinimumMatrixDomination
#859	ExactCoverBy3Sets → AlgebraicEquationsOverGF2	AlgebraicEquationsOverGF2
#860	ExactCoverBy3Sets → MinimumWeightSolutionToLinearEquations	MinimumWeightSolutionToLinearEquations
#862	KSatisfiability(K3) → OneInThreeSatisfiability	OneInThreeSatisfiability
#868	Satisfiability → NonTautology	NonTautology
#882	KSatisfiability(K3) → Kernel	Kernel
#884	KSatisfiability(K3) → MonochromaticTriangle	MonochromaticTriangle
#889	PartitionIntoCliques → MinimumCoveringByCliques	PartitionIntoCliques + MinimumCoveringByCliques
#893	MinimumVertexCover (cubic) → MinimumMaximalMatching	MinimumMaximalMatching
#911	HamiltonianPath → DegreeConstrainedSpanningTree	DegreeConstrainedSpanningTree
#913	ExactCoverBy3Sets → BoundedDiameterSpanningTree	BoundedDiameterSpanningTree
#918	KSatisfiability(K3) → CyclicOrdering	CyclicOrdering

Newly unblocked by earlier PRs (9):

#	Source → Target	Unblocked by
#395	Partition → KthLargestMTuple	KthLargestMTuple (PR #805)
#475	RegisterSufficiency → SeqMinMaxCumulativeCost	RegisterSufficiency (PR #816)
#488	Partition → ProductionPlanning	ProductionPlanning (pre-existing)
#521	SubsetSum → IntegerKnapsack	IntegerKnapsack (PR #815)
#569	SubsetSum → IntegerExpressionMembership	IntegerExpressionMembership (PR #814)
#781	IntegerKnapsack → ILP	IntegerKnapsack (PR #815)
#782	RegisterSufficiency → ILP	RegisterSufficiency (PR #816)
#784	FeasibleBasisExtension → ILP	FeasibleBasisExtension (PR #818)
#872	KSatisfiability(K3) → RegisterSufficiency	RegisterSufficiency (PR #816)

Needs fix (16)

#	Source → Target	Notes
#166	KSatisfiability → MaxCut	Threshold formula inconsistent
#277	Dir2CommodityFlow → Undir2CommodityFlow	Empty body
#363	Partition → IntegralFlowWithMultipliers	Counterexample
#459	MinimumVertexCover → MinimumCardinalityKey	FDs wrong
#523	KClique → PartiallyOrderedKnapsack	Reverse direction fails
#472	OptimalLinearArrangement → SeqMinWeightedCompletion	Bound K undefined
#385	MinimumVertexCover → ComparativeContainment	Direction backwards
#423	Partition → ExpectedRetrievalCost	Degenerate
#460	MinimumHittingSet → AdditionalKey	FDs broken
#462	MinimumHittingSet → BoyceCoddNormalFormViolation	FDs broken
#250	MinimumVertexCover → MinimumCutIntoBoundedSets	Self-contradictory
#435	HamiltonianPath → ConsecutiveBlockMinimization	Construction fails
#436	HamiltonianPath → ConsecutiveSets	Same as #435
#461	MinimumCardinalityKey → PrimeAttributeName	Incomplete
#425	MinimumVertexCover → MultipleCopyFileAllocation	Needs cleanup
#206	KClique → MinimumTardinessSequencing	Decision/optimization mismatch

---

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

High confidence (4 + 7 newly unblocked)

#	Source → Target	G&J Ref
#198	MinimumVertexCover → HamiltonianCircuit	Thm 3.4
#368	KSatisfiability(K3) → Dir2CommodityIntegralFlow	ND38
#370	KSatisfiability(K3) → DisjointConnectingPaths	ND40
#476	KSatisfiability(K3) → PrecedenceConstrainedScheduling	SS9

Newly unblocked complex:

#	Source → Target	Unblocked by
#377	Planar3Satisfiability → MinimumGeometricConnectedDominatingSet	Both models
#479	KSatisfiability(K3) → PreemptiveScheduling	PreemptiveScheduling
#553	KSatisfiability(K3) → QuadraticCongruences	QuadraticCongruences
#554	KSatisfiability(K3) → SimultaneousIncongruences	SimultaneousIncongruences
#905	KSatisfiability(K3) → FeasibleRegisterAssignment	FeasibleRegisterAssignment
#920	KSatisfiability(K3) → NonLivenessFreePetriNet	NonLivenessFreePetriNet

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	MinimumVertexCover → ShortestCommonSupersequence	SR8
#429	MinimumVertexCover → LongestCommonSubsequence	SR10
#478	MinimumVertexCover → 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	MinimumVertexCover → MinimumDummyActivitiesPert	ND44
#383	MinimumVertexCover → 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

---

Tier 2 — Blocked (~52 issues)

Remaining issues where at least one model is missing. Major blockers:

Missing model	Blocked issues
Maximum2Satisfiability	#825, #863, #864, #886
NumericalMatchingWithTargetSums	#391, #827
ThreeMatroidIntersection	#386, #857
Various scheduling (NoWaitFlowShop, TwoProcessorFlowShop)	#483, #484
Various graph (NetworkReliability, DirectedHamiltonianCircuit, etc.)	~12 issues
Various DB/misc (Monotone3SAT, SerializabilityOfDBHistories, etc.)	~6 issues
Code generation models	#874, #904, #907, #908
Various algebra/set (SimultaneousDivisibility, SquareTiling, etc.)	~6 issues
Various storage/compression	~8 issues

---

Special Flags

#	Notes
#236	Turing reduction — cannot implement as ReduceTo<T>
#361	Turing reduction
#369	Duplicate of #277 — close

Potential Duplicates (6 pairs)

New	Old	Rule
#828	#397	ThreePartition → DynamicStorageAllocation
#827	#391	Numerical3DM → NumericalMatchingWithTargetSums
#826	#390	3DM → Numerical3DM
#824	#389	3DM → ThreePartition
#858	#388	X3C → SubsetProduct
#857	#386	3DM → ThreeMatroidIntersection

---

Next Batch — Priority Order

1. Highest leverage (2): [Rule] SUBSET SUM to PARTITION #973 (SubsetSum→Partition, unlocks ~12 problems), [Rule] VERTEX COVER to HAMILTONIAN CIRCUIT #198 (MVC→HamiltonianCircuit, unlocks ~9 problems)
2. Simple Tier 1a (4): [Rule] DOMINATING SET to MIN-MAX MULTICENTER #379, [Rule] DOMINATING SET to MIN-SUM MULTICENTER #380, [Rule] OPTIMAL LINEAR ARRANGEMENT to ROOTED TREE ARRANGEMENT #888, [Rule] X3C to ACYCLIC PARTITION #822
3. High-value newly unblocked (10): [Rule] NOT-ALL-EQUAL 3SAT to SET SPLITTING #382/[Rule] NOT-ALL-EQUAL 3SAT to SET SPLITTING #841 (NAE-SAT→SetSplitting), [Rule] 3SAT to ONE-IN-THREE 3SAT #862 (3SAT→1-in-3-SAT), [Rule] SATISFIABILITY to NON-TAUTOLOGY #868 (SAT→NonTautology), [Rule] SET SPLITTING to BETWEENNESS #842 (SetSplitting→Betweenness), [Rule] GRAPH K-COLORABILITY to PARTITION INTO CLIQUES #844 (KColoring→PartitionIntoCliques), [Rule] PARTITION INTO CLIQUES to MinimumCoveringByCliques #889 (PartitionIntoCliques→MinCoveringByCliques), [Rule] VERTEX COVER (cubic) to MINIMUM MAXIMAL MATCHING #893 (MVC→MinMaximalMatching), [Rule] MINIMUM MAXIMAL MATCHING to MaximumAchromaticNumber #846, [Rule] MINIMUM MAXIMAL MATCHING to MinimumMatrixDomination #847
4. Remaining Tier 1b moderate: [Rule] VERTEX COVER to HAMILTONIAN PATH #892, [Rule] VERTEX COVER to PARTIAL FEEDBACK EDGE SET #894, [Rule] MAX CUT to OPTIMAL LINEAR ARRANGEMENT #890
5. Other newly unblocked moderate: [Rule] Partition to Sequencing to Minimize Tardy Task Weight #471, [Rule] Partition to Sequencing with Deadlines and Set-Up Times #474, [Rule] Partition to Open-Shop Scheduling #481, [Rule] HamiltonianPath to DegreeConstrainedSpanningTree #911, [Rule] ExactCoverBy3Sets to BoundedDiameterSpanningTree #913, [Rule] X3C to ALGEBRAIC EQUATIONS OVER GF[2] #859, [Rule] X3C to MinimumWeightSolutionToLinearEquations #860, [Rule] 3-SATISFIABILITY to KERNEL #882, [Rule] 3-SATISFIABILITY to MONOCHROMATIC TRIANGLE #884, [Rule] 3-Satisfiability to Cyclic Ordering #918
6. ILP rules (2): [Rule] SchedulingToMinimizeWeightedCompletionTime to ILP #783, [Rule] IntegerKnapsack to ILP #781
7. Housekeeping: Close [Rule] IntegralFlowHomologousArcs → ILP #733, [Rule] TimetableDesign to ILP #728, [Rule] DIRECTED TWO-COMMODITY INTEGRAL FLOW to UNDIRECTED TWO-COMMODITY INTEGRAL FLOW #369; resolve 6 remaining duplicate pairs

Note: Run topology-sanity-check redundancy <source> <target> before implementing any rule.

---

Legacy — Implemented Rules (53 closed)

See git history and closed [Rule] issues for the full list of implemented rules across PRs #777, #779, #804, #972, and others.

PR #972 (10 rules): #396, #469, #473, #477, #482, #485, #769, #821, #823, #849

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