Complete missing example-db and paper entries for 43 rules from #770 #974
Description
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:
- PR feat: add 8 Tier 1a reduction rules (#770) #777 has entries for:
ConsecutiveOnesMatrixAugmentation → ILP,HamiltonianCircuit → TravelingSalesman - PR feat: add 11 Tier 1a + 1b medium-confidence reduction rules (#770) #804 has entries for all 11 rules
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
- 31 rules have canonical example builders in
src/example_db/rule_builders.rs(check 9) - 43 rules have lookup tests in
src/unit_tests/example_db.rs(check 10) - 30 rules have
reduction-rule(...)entries indocs/paper/reductions.typ(check 11) -
make checkpasses -
make paperbuilds successfully - Structural review reports all 43 rules passing checks 9-11