Audit: Completeness gaps in models and rules

[GiggleLiu]

Summary

A systematic audit of all 21 models and 38 rules (31 standard + 7 cast/variant) was performed using the review-implementation skill checklist. This issue documents all gaps found.

Model Audit Results

21 models checked, 336 total checks, 11 failures across 6 models.

Priority 1: MaximalIS — Missing CLI dispatch + paper entries (4 failures)

MaximalIS is fully implemented (code, tests, serde, mod.rs registration) but:

• Missing load_problem match arm in problemreductions-cli/src/dispatch.rs — pred load will fail for this problem
• Missing serialize_any_problem match arm in problemreductions-cli/src/dispatch.rs — reduction output serialization will fail
• Missing display-name entry in docs/paper/reductions.typ
• Missing #problem-def("MaximalIS") block in docs/paper/reductions.typ

Priority 2: Missing models/mod.rs re-exports (3 models)

These types are accessible via prelude::* but missing from pub use in src/models/mod.rs:

• MaximumClique — not in pub use graph::{...}
• ILP — not in pub use optimization::{...}
• KSatisfiability — not in pub use satisfiability::{...}

Users importing directly from models:: (rather than prelude::*) would get compile errors.

Priority 3: Missing paper entries (3 models)

These models have no mathematical definition in docs/paper/reductions.typ:

• BMF — missing display-name + #problem-def
• PaintShop — missing display-name + #problem-def
• BicliqueCover — missing display-name + #problem-def

Models with all 16 checks passing (15/21)

MaxCut, MaximumIndependentSet, MaximumMatching, MinimumDominatingSet, MinimumVertexCover, TravelingSalesman, KColoring, SpinGlass, QUBO, Satisfiability, MaximumSetPacking, MinimumSetCovering, Factoring, CircuitSAT, MaximumClique (code-only — all but re-export pass).

---

Rule Audit Results

31 standard rules + 7 cast rules checked.

Priority 1: sat_circuitsat — Missing example + paper entry (6 failures)

Satisfiability → CircuitSAT has a complete rule implementation with passing closed-loop test, but:

• Missing example file examples/reduction_satisfiability_to_circuitsat.rs
• Missing example_test! registration in tests/suites/examples.rs
• Missing example_fn! registration in tests/suites/examples.rs
• Missing reduction-rule("Satisfiability", "CircuitSAT") in docs/paper/reductions.typ

Priority 1: Reverse-direction reductions missing examples (2 rules)

These bidirectional rules have the reverse direction registered via #[reduction] and paper entries, but no example programs:

• MaximumSetPacking → MaximumIndependentSet — no example file, no example_test!/example_fn! registration
• KSatisfiability → Satisfiability — no example file, no example_test!/example_fn! registration

Priority 2: Cast rules missing test files (5 rules)

All 5 _casts rules use impl_variant_reduction! macro and lack dedicated test files:

• ksatisfiability_casts — no #[path] link, no test file
• spinglass_casts — no #[path] link, no test file
• maximumindependentset_casts — no #[path] link, no test file
• kcoloring_casts — no #[path] link, no test file
• maximumsetpacking_casts — no #[path] link, no test file

Note: These are trivial identity-mapping reductions generated by macro. The structural variant rules (maximumindependentset_gridgraph, maximumindependentset_triangular) do have full test coverage.

Priority 3: Test naming convention — closed_loop suffix (20 rules)

20 out of 31 standard rules don't follow the test_<source>_to_<target>_closed_loop naming convention. Most DO have equivalent correctness tests (e.g., test_ilp_solution_equals_brute_force_*), just without the conventional name. Affected rules:

Click to expand full list

1. minimumvertexcover_maximumindependentset
2. spinglass_qubo
3. spinglass_maxcut
4. sat_maximumindependentset
5. sat_minimumdominatingset
6. sat_ksat
7. sat_coloring
8. factoring_circuit
9. factoring_ilp
10. maximumindependentset_ilp
11. minimumvertexcover_ilp
12. maximumclique_ilp
13. minimumdominatingset_ilp
14. maximummatching_ilp
15. maximumsetpacking_ilp
16. minimumsetcovering_ilp
17. coloring_ilp
18. circuit_spinglass
19. maximumindependentset_maximumsetpacking
20. maximummatching_maximumsetpacking
21. minimumvertexcover_minimumsetcovering

Rules with all 14 checks passing (10/31)

maximumindependentset_qubo, minimumvertexcover_qubo, ksatisfiability_qubo, maximumsetpacking_qubo, ilp_qubo, coloring_qubo, circuit_ilp, travelingsalesman_ilp, qubo_ilp, sat_circuitsat (code-only).

---

Summary Statistics

Category	Total Checks	Pass	Fail	Pass Rate
Models (21)	336	325	11	96.7%
Standard Rules (31)	434	408	26	94.0%
Cast Rules (7)	35	25	10	71.4%

Suggested Action Items

1. Fix MaximalIS CLI dispatch — functional bug, pred cannot load this problem
2. Add sat_circuitsat example + paper entry — completeness gap
3. Add examples for 2 reverse-direction rules — MaximumSetPacking→MIS, KSatisfiability→SAT
4. Add models/mod.rs re-exports — MaximumClique, ILP, KSatisfiability
5. Add paper entries for 4 models — MaximalIS, BMF, PaintShop, BicliqueCover
6. Consider adding cast rule tests — low priority, macro-generated code
7. Standardize test naming — rename existing tests to use closed_loop suffix (low priority, cosmetic)