[Meta] Connect isolated problem types to the reduction graph

[GiggleLiu]

Summary

Running cargo run --example detect_isolated_problems reveals 7 problem types that have no reduction rules connecting them to the main graph. They are registered with variants and complexity but cannot be reached from (or reduce to) any other problem.

Isolated Problems

Problem	Variants	Category	Notes
BMF (Binary Matrix Factorization)	1	algebraic	No issues filed
BicliqueCover	1	graph	No issues filed
BinPacking	2 (f64, i32)	misc	#396 exists (PARTITION → BIN PACKING) but PARTITION is not yet in the graph
ClosestVectorProblem	2 (f64, i32)	algebraic	No issues filed
Knapsack	1	misc	#521–#523 exist for new Knapsack variants, but none connect the existing Knapsack model
MaximalIS	1	graph	No issues filed
PaintShop	1	misc	No issues filed

Suggested Reductions

Each isolated problem needs at least one incoming or outgoing reduction to join the main component. Well-known reductions from the literature:

• Knapsack → ILP — direct formulation as integer linear program (textbook reduction)
• BinPacking → ILP — standard bin packing ILP formulation
• MaximalIS ↔ MaximumIndependentSet — every MIS is a maximal IS; enumerate maximal to find maximum
• ClosestVectorProblem → ILP — CVP can be formulated as an ILP over lattice coefficients
• PaintShop → QUBO — paint shop problem has known QUBO formulations
• BMF → ILP — binary matrix factorization can be encoded as a 0-1 integer program
• BicliqueCover → SAT / BicliqueCover → ILP — set-cover-like formulations

Context

The main connected component contains 17 problem types with 52 reductions. Adding even one reduction per isolated problem would make the entire graph connected.

Detected by: examples/detect_isolated_problems.rs

[GiggleLiu]

NP-hardness proof chain check (3-SAT reachability)

Beyond undirected connectivity, we can verify that the reduction graph encodes an NP-hardness proof for each problem by checking directed reachability from 3-SAT (KSatisfiability K3).

Results

Running pred from 3SAT --hops 20 shows 3-SAT can reach 13 problem types (via directed reductions). Three NP-hard problems in the main component are not reachable from 3-SAT:

Problem	NP-hard?	Reachable from 3-SAT?	Gap
MaximumClique	Yes	No	Missing incoming reduction (e.g., 3-SAT → MaxClique)
TravelingSalesman	Yes	No	Missing incoming reduction (e.g., 3-SAT → HamiltonianCycle → TSP)
SubsetSum	Yes (NP-complete)	No	Missing incoming reduction (e.g., 3-SAT → SubsetSum)

Correctly unreachable (not NP-hard)

These are correctly not reachable from 3-SAT:

Problem	Reason
MaximumMatching	In P (polynomial-time, Edmonds' algorithm)
KSatisfiability K2	2-SAT is in P
KColoring K2	2-Coloring is in P
Factoring	Not known to be NP-complete (intermediate complexity)

Suggestion

Add this as a third check in the topology-sanity-check skill and the detect_isolated_problems example — it catches real proof-chain gaps that orphan detection misses.