Summary
PRs #777, #779, #804, and #972 (all from #770) shipped 43 reduction rules with complete core implementations (checks 1-8 pass for all), but systematically missed documentation and example-db components. This issue tracks completing the missing structural checklist items.
Debt Inventory
Check 9 — Canonical rule example in rule_builders.rs (31/43 missing)
PR #777 (10 rules missing):
ConsecutiveOnesMatrixAugmentation → ILPExactCoverBy3Sets → StaffSchedulingHamiltonianCircuit → BottleneckTravelingSalesmanHamiltonianCircuit → HamiltonianPathHamiltonianCircuit → TravelingSalesmanHamiltonianPath → IsomorphicSpanningTreeKClique → ConjunctiveBooleanQueryKClique → SubgraphIsomorphismPartition → MultiprocessorSchedulingSatisfiability → NAESatisfiability
PR #804 (11 rules missing):
HamiltonianCircuit → LongestCircuitKClique → BalancedCompleteBipartiteSubgraphKColoring → TwoDimensionalConsecutiveSetsLongestCommonSubsequence → MaximumIndependentSetMinimumVertexCover → EnsembleComputationMinimumVertexCover → MinimumHittingSetPaintShop → QUBOPartition → SubsetSumPartitionIntoPathsOfLength2 → BoundedComponentSpanningForestRootedTreeArrangement → RootedTreeStorageAssignmentSubsetSum → CapacityAssignment
PR #972 (10 rules missing):
ExactCoverBy3Sets → MaximumSetPackingILP/i32 → ILP/boolMaxCut → MinimumCutIntoBoundedSetsNAESatisfiability → MaxCutPartition → BinPackingThreePartition → FlowShopSchedulingThreePartition → JobShopSchedulingThreePartition → ResourceConstrainedSchedulingThreePartition → SequencingToMinimizeWeightedTardinessThreePartition → SequencingWithReleaseTimesAndDeadlines
Check 10 — Example-db lookup test in example_db.rs (43/43 missing)
All 43 rules across all 4 PRs. Includes all rules listed above for check 9, plus the 12 PR #779 rules:
HamiltonianCircuit → BiconnectivityAugmentationHamiltonianCircuit → QuadraticAssignmentHamiltonianCircuit → RuralPostmanHamiltonianCircuit → StackerCraneHamiltonianCircuit → StrongConnectivityAugmentationHamiltonianPath → ConsecutiveOnesSubmatrixKSatisfiability → KCliqueKSatisfiability → MinimumVertexCoverMaximumIndependentSet → IntegralFlowBundlesMinimumVertexCover → MinimumFeedbackArcSetPartition → SequencingWithinIntervalsPartition → ShortestWeightConstrainedPath
Check 11 — Paper reduction-rule entry in reductions.typ (30/43 missing)
All 43 rules minus the 13 that already have entries:
Missing from PR #777 (8 rules):
ExactCoverBy3Sets → StaffSchedulingHamiltonianCircuit → BottleneckTravelingSalesmanHamiltonianCircuit → HamiltonianPathHamiltonianPath → IsomorphicSpanningTreeKClique → ConjunctiveBooleanQueryKClique → SubgraphIsomorphismPartition → MultiprocessorSchedulingSatisfiability → NAESatisfiability
Missing from PR #779 (12 rules):
HamiltonianCircuit → BiconnectivityAugmentationHamiltonianCircuit → QuadraticAssignmentHamiltonianCircuit → RuralPostmanHamiltonianCircuit → StackerCraneHamiltonianCircuit → StrongConnectivityAugmentationHamiltonianPath → ConsecutiveOnesSubmatrixKSatisfiability → KCliqueKSatisfiability → MinimumVertexCoverMaximumIndependentSet → IntegralFlowBundlesMinimumVertexCover → MinimumFeedbackArcSetPartition → SequencingWithinIntervalsPartition → ShortestWeightConstrainedPath
Missing from PR #972 (10 rules):
ExactCoverBy3Sets → MaximumSetPackingILP/i32 → ILP/boolMaxCut → MinimumCutIntoBoundedSetsNAESatisfiability → MaxCutPartition → BinPackingThreePartition → FlowShopSchedulingThreePartition → JobShopSchedulingThreePartition → ResourceConstrainedSchedulingThreePartition → SequencingToMinimizeWeightedTardinessThreePartition → SequencingWithReleaseTimesAndDeadlines
Root Cause
The review-structural skill checklist had checks 9-11 defined, but the review-pipeline agent either did not run the full checklist (PRs #777, #779) or classified failures as non-blocking (#972). PR #804 was the only PR that ran the /issue-to-pr skill upfront, which produced paper entries — but even it missed checks 9 and 10.
Acceptance Criteria
Summary
PRs #777, #779, #804, and #972 (all from #770) shipped 43 reduction rules with complete core implementations (checks 1-8 pass for all), but systematically missed documentation and example-db components. This issue tracks completing the missing structural checklist items.
Debt Inventory
Check 9 — Canonical rule example in
rule_builders.rs(31/43 missing)PR #777 (10 rules missing):
ConsecutiveOnesMatrixAugmentation → ILPExactCoverBy3Sets → StaffSchedulingHamiltonianCircuit → BottleneckTravelingSalesmanHamiltonianCircuit → HamiltonianPathHamiltonianCircuit → TravelingSalesmanHamiltonianPath → IsomorphicSpanningTreeKClique → ConjunctiveBooleanQueryKClique → SubgraphIsomorphismPartition → MultiprocessorSchedulingSatisfiability → NAESatisfiabilityPR #804 (11 rules missing):
HamiltonianCircuit → LongestCircuitKClique → BalancedCompleteBipartiteSubgraphKColoring → TwoDimensionalConsecutiveSetsLongestCommonSubsequence → MaximumIndependentSetMinimumVertexCover → EnsembleComputationMinimumVertexCover → MinimumHittingSetPaintShop → QUBOPartition → SubsetSumPartitionIntoPathsOfLength2 → BoundedComponentSpanningForestRootedTreeArrangement → RootedTreeStorageAssignmentSubsetSum → CapacityAssignmentPR #972 (10 rules missing):
ExactCoverBy3Sets → MaximumSetPackingILP/i32 → ILP/boolMaxCut → MinimumCutIntoBoundedSetsNAESatisfiability → MaxCutPartition → BinPackingThreePartition → FlowShopSchedulingThreePartition → JobShopSchedulingThreePartition → ResourceConstrainedSchedulingThreePartition → SequencingToMinimizeWeightedTardinessThreePartition → SequencingWithReleaseTimesAndDeadlinesCheck 10 — Example-db lookup test in
example_db.rs(43/43 missing)All 43 rules across all 4 PRs. Includes all rules listed above for check 9, plus the 12 PR #779 rules:
HamiltonianCircuit → BiconnectivityAugmentationHamiltonianCircuit → QuadraticAssignmentHamiltonianCircuit → RuralPostmanHamiltonianCircuit → StackerCraneHamiltonianCircuit → StrongConnectivityAugmentationHamiltonianPath → ConsecutiveOnesSubmatrixKSatisfiability → KCliqueKSatisfiability → MinimumVertexCoverMaximumIndependentSet → IntegralFlowBundlesMinimumVertexCover → MinimumFeedbackArcSetPartition → SequencingWithinIntervalsPartition → ShortestWeightConstrainedPathCheck 11 — Paper
reduction-ruleentry inreductions.typ(30/43 missing)All 43 rules minus the 13 that already have entries:
ConsecutiveOnesMatrixAugmentation → ILP,HamiltonianCircuit → TravelingSalesmanMissing from PR #777 (8 rules):
ExactCoverBy3Sets → StaffSchedulingHamiltonianCircuit → BottleneckTravelingSalesmanHamiltonianCircuit → HamiltonianPathHamiltonianPath → IsomorphicSpanningTreeKClique → ConjunctiveBooleanQueryKClique → SubgraphIsomorphismPartition → MultiprocessorSchedulingSatisfiability → NAESatisfiabilityMissing from PR #779 (12 rules):
HamiltonianCircuit → BiconnectivityAugmentationHamiltonianCircuit → QuadraticAssignmentHamiltonianCircuit → RuralPostmanHamiltonianCircuit → StackerCraneHamiltonianCircuit → StrongConnectivityAugmentationHamiltonianPath → ConsecutiveOnesSubmatrixKSatisfiability → KCliqueKSatisfiability → MinimumVertexCoverMaximumIndependentSet → IntegralFlowBundlesMinimumVertexCover → MinimumFeedbackArcSetPartition → SequencingWithinIntervalsPartition → ShortestWeightConstrainedPathMissing from PR #972 (10 rules):
ExactCoverBy3Sets → MaximumSetPackingILP/i32 → ILP/boolMaxCut → MinimumCutIntoBoundedSetsNAESatisfiability → MaxCutPartition → BinPackingThreePartition → FlowShopSchedulingThreePartition → JobShopSchedulingThreePartition → ResourceConstrainedSchedulingThreePartition → SequencingToMinimizeWeightedTardinessThreePartition → SequencingWithReleaseTimesAndDeadlinesRoot Cause
The
review-structuralskill checklist had checks 9-11 defined, but the review-pipeline agent either did not run the full checklist (PRs #777, #779) or classified failures as non-blocking (#972). PR #804 was the only PR that ran the/issue-to-prskill upfront, which produced paper entries — but even it missed checks 9 and 10.Acceptance Criteria
src/example_db/rule_builders.rs(check 9)src/unit_tests/example_db.rs(check 10)reduction-rule(...)entries indocs/paper/reductions.typ(check 11)make checkpassesmake paperbuilds successfully