Strategy for checking and adding reduction rules

[zazabap]

Current state

Metric	Count
Problem types	115
Reduction edges	139
Connected components	21
Main component size	95
Isolated problems (zero reductions)	20
NP-hard problems unreachable from 3-SAT	76

Recent work: 63 ILP reductions (#763, #767), CustomizedSolver (#766), aggregation unification (#754). Refactoring (#765, #748) planned separately.

Open question: how should we grow the reduction graph with high confidence that each added rule is correct, non-trivial, and useful to domain experts?

Backlog

241 open issues on the project board, mostly from Garey & Johnson (1979):

Category	Count	Status
[Rule] labeled Good	19	Reviewed, ready
[Rule] unlabeled	131	Not yet reviewed
[Rule] labeled PoorWritten	4	Needs rewriting
[Model] labeled Good	8	Ready
[Model] labeled PoorWritten	32	Needs rewriting
[Model] unlabeled	3	Not yet reviewed
Labeled Wrong	12	Incorrect
Labeled Useless	6	No value
Other (architecture, enhancements)	26	Separate track

131 rule issues are unreviewed. The write-ups may not faithfully capture the original G&J constructions.

Proposed plan

1. Rule priority — what's worth implementing?

Priority	Criterion
P0	Connects an isolated problem to the main component (20 orphans)
P1	Closes an NP-hardness proof gap from 3-SAT (76 unreachable)
P2	Provides a solver path to ILP, QUBO, or customized solver
P3	Well-known in the literature (Karp's 21, textbook standard)
P4	Exists in G&J but not commonly cited

A rule must satisfy at least one criterion. Higher-priority rules first.

Agree with this ranking? Reorder, add, or remove?

2. Verification bar — what do we require before merging?

Requirement	When
Closed-loop tests + overhead verification + >95% coverage	Always (existing)
(A) Literature citation — G&J section or paper reference	Always
(B) Proof sketch in docs/paper/reductions.typ	Always
(C) Expert sanity check — reviewer confirms construction	Complex gadgets or obscure sources

Is (A)+(B) always too heavy? Is (C) needed more broadly? Or is tests-only sufficient?

3. Triage strategy for 131 unlabeled rule issues

1. Start with the 19 Good rules — already reviewed
2. Demand-driven: when we need a connection (orphan, proof gap, solver path), pull the issue, review, then implement
3. Batch-triage by domain when going deep on a domain (see Q4)
4. Close the 12 Wrong + 6 Useless issues — misleading as-is

Agree with closing Wrong/Useless? Should we salvage any first? Is demand-driven the right pace?

4. Domain focus order

Order	Domain	Orphans to connect	Good rules
1st	Graph optimization (MIS, coloring, cuts, flows, Hamiltonian)	BicliqueCover, MaximalIS, PaintShop	~12
2nd	Packing/covering (set cover, bin packing, knapsack)	Knapsack, BinPacking, BMF	~4
3rd	Scheduling (flow shop, job shop, multiprocessor)	StaffScheduling	~3

Does this order make sense? Should a different domain go first?

Related issues

• [Meta] Connect isolated problem types to the reduction graph #610 — Connect isolated problem types
• Upgrade 17 decision models to optimization versions #765 — Decision→optimization upgrades
• [Architecture] DefaultSolver per problem — flexible solver dispatch #748 — DefaultSolver per problem

cc @GiggleLiu @isPANN

[zazabap]

On the role of /check-issue in the proposed plan

/check-issue is our automated quality gate — 4 checks per issue (usefulness, non-triviality, correctness, writing quality) with labels and structured reports. Here's how it maps to the plan above and where it falls short.

What it covers

Plan item	/check-issue support
Q1 Priority ranking	Partial — detects redundancy (path already exists) and orphan connections, but cannot judge P3/P4 (literature importance, domain value)
Q2 Verification (A) citation	Yes — checks whether cited papers exist via web search + knowledge base
Q2 Verification (B) proof sketch	No — checks issue write-up completeness, not paper content
Q2 Verification (C) expert check	No — cannot replace human judgment on construction correctness
Q3 Triage	Yes — the primary tool for labeling Good/Wrong/PoorWritten/Useless/Trivial
Q4 Domain focus	No — domain selection is a human decision

Key limitations

1. G&J literature gap. Many 1979 reductions are not digitized. The correctness check may produce false Wrong labels when it can't find an online source — even though the reduction is well-established in the physical book. This matters for the 131 unlabeled issues.

2. Cannot verify mathematical correctness. A well-written issue with a plausible but subtly wrong gadget construction would pass. If we adopt verification level (B) or (C), that's human work beyond what the skill provides.

3. Batch cost. Each invocation does web searches, CLI calls, and posts a comment. Running on all 131 unlabeled issues would be expensive — consistent with the demand-driven triage proposed in Q3 rather than a systematic sweep.

Suggested improvements

• For G&J issues: Accept "G&J Section X.Y, Problem [NAME]" as a valid citation without requiring a web-findable source. This avoids false Wrong labels on well-established reductions.
• For priority scoring: Could extend the usefulness check to output a priority tier (P0–P4) based on whether the rule connects an orphan, closes a proof gap, or provides a solver path — aligning with the Q1 ranking.
• For batch triage: A lightweight "quick-check" mode that only runs the redundancy and template checks (skipping expensive web searches) would make domain-batch triage (Q3 option 3) more practical.

Thoughts on whether these improvements are worth pursuing?

[zazabap]

Dispatch sub-agent to find the reliable source for each rule. Must be the book resource, give a rank for the high-confidence, easy reduction and avoid redundant rule. Must be a form and which reduction rules to be realize first.

[zazabap]

No longer available due to the new issue opened #770