Problem Reductions

problem-reductions is a rust library that provides implementations of various computational hard problems and reduction rules between them. It is designed for algorithm research, education, and industry applications.

Reduction Graph

You can also explore this graph from the terminal with the CLI tool. For theoretical background and correctness proofs, see the PDF manual.

Our Vision

Computational complexity theory has produced a rich body of polynomial-time reductions between NP-hard problems, yet these results largely remain confined to papers. The gap between theoretical algorithms and working software leads to two persistent inefficiencies:

• Solver underutilization. State-of-the-art solvers (SAT solvers, ILP solvers, QUBO annealers) each target a single problem formulation. In principle, any problem reducible to that formulation can leverage the same solver — but without a systematic reduction library, practitioners must re-derive and re-implement each transformation.
• Redundant effort. Problems that are polynomial-time equivalent are, from a computational standpoint, interchangeable. Without infrastructure connecting them, the same algorithmic insights are independently reimplemented across domains.

Our goal is to build a comprehensive, machine-readable reduction graph: a directed graph in which every node is a computational problem and every edge is a verified polynomial-time reduction. Given such a graph, one can automatically compose reduction paths to route any source problem to any reachable target solver.

A key enabler is AI-assisted implementation. We propose a pipeline of algorithm → paper → software, in which AI agents translate published reduction proofs into tested code. The critical question — can AI-generated reductions be trusted? — has a concrete answer: nearly all reductions admit closed-loop verification. A round-trip test reduces a source instance to a target, solves the target, extracts the solution back, and checks it against a direct solve of the source. This property makes correctness mechanically verifiable, independent of how the code was produced.

This library is the foundation of that effort: an open-source, extensible reduction graph with verified implementations, designed for contributions from both human researchers and AI agents.

Call for Contributions

No programming experience required. You contribute domain knowledge — we handle the implementation.

How it works

1. File an issue — use the Problem or Rule template. Describe the problem or reduction you have in mind; the template guides you through the details.
2. We implement it — for reasonable requests, maintainers tag the issue implement and AI agents generate a tested implementation.
3. We present it to you — all issue contributors are invited to community calls (via Zulip), where maintainers walk through the implementation — documentation, CLI behavior, correctness — and you provide feedback.

Authorship

Contribute 10 non-trivial reduction rules and you'll be added to the author list of the paper.

For manual implementation, see the Design guide.

License

MIT License

Getting Started

What This Library Does

problem-reductions transforms hard computational problems into forms that efficient solvers can handle. You define a problem, reduce it to another problem type (like QUBO or ILP), solve the reduced problem, and extract the solution back. The interactive reduction graph shows all available problem types and transformations.

Installation

Add to your Cargo.toml:

[dependencies]
problemreductions = "0.2"

The Reduction Workflow

The core workflow is: create a problem, reduce it to a target, solve the target, and extract the solution back.

Example 1: Direct reduction — Set Packing to ILP

Reduce Maximum Set Packing to Integer Linear Programming (ILP), solve with the ILP solver, and extract the solution back.

Step 1 — Create the source problem

A small set system with pairwise overlaps gives a direct binary ILP.

use problemreductions::prelude::*;
use problemreductions::models::algebraic::ILP;
use problemreductions::solvers::ILPSolver;

let problem = MaximumSetPacking::<i32>::new(vec![
    vec![0, 1],
    vec![1, 2],
    vec![2, 3],
    vec![4, 5],
]);

Step 2 — Reduce to ILP

ReduceTo applies a single-step reduction. The result holds the target problem and knows how to map solutions back. The ILP formulation introduces binary variable x_i for each set, constraint x_i + x_j ≤ 1 for each overlapping pair, and maximizes the weighted sum.

let reduction = ReduceTo::<ILP>::reduce_to(&problem);
let ilp = reduction.target_problem();
println!("ILP: {} variables, {} constraints", ilp.num_vars, ilp.constraints.len());

ILP: 4 variables, 2 constraints

Step 3 — Solve the ILP

ILPSolver uses the HiGHS solver to find optimal solutions efficiently. For small instances you can also use BruteForce, but ILPSolver scales to much larger problems.

let solver = ILPSolver::new();
let ilp_solution = solver.solve(ilp).unwrap();
println!("ILP solution: {:?}", ilp_solution);

ILP solution: [1, 0, 1, 0]

Step 4 — Extract and verify

extract_solution maps the ILP solution back to the original problem's configuration space.

let solution = reduction.extract_solution(&ilp_solution);
let metric = problem.evaluate(&solution);
println!("Packing solution: {:?} -> size {:?}", solution, metric);
assert!(metric.is_valid());

Packing solution: [1, 0, 1, 1] -> size Valid(3)

For convenience, ILPSolver::solve_reduced combines reduce + solve + extract in a single call:

let solution = ILPSolver::new().solve_reduced(&problem).unwrap();
assert!(problem.evaluate(&solution).is_valid());

Example 2: Reduction path search — integer factoring to spin glass

Real-world problems often require chaining multiple reductions. Here we factor the integer 6 by reducing Factoring through the reduction graph to SpinGlass, through automatic reduction path search. (full source)

Let's walk through each step.

Step 1 — Discover the reduction path

ReductionGraph holds every registered reduction. find_cheapest_path searches for the shortest chain from a source problem variant to a target variant.

    let graph = ReductionGraph::new(); // all registered reductions
    let src_var = ReductionGraph::variant_to_map(&Factoring::variant()); // {} (no variant params)
    let dst_var = ReductionGraph::variant_to_map(&SpinGlass::<SimpleGraph, f64>::variant()); // {graph: "SimpleGraph", weight: "f64"}
    let rpath = graph
        .find_cheapest_path(
            "Factoring",               // source problem name
            &src_var,                  // source variant map
            "SpinGlass",               // target problem name
            &dst_var,                  // target variant map
            &ProblemSize::new(vec![]), // input size (empty = unknown)
            &MinimizeSteps,            // cost function: fewest hops
        )
        .unwrap();
    println!("  {}", rpath);

  Factoring → CircuitSAT → SpinGlass {graph: "SimpleGraph", weight: "i32"}

Step 2 — Create the Factoring problem

Factoring::new(m, n, target) creates a factoring instance: find two factors p (m-bit) and q (n-bit) such that p × q = target. Here we factor 6 with two 2-bit factors, expecting 2 × 3 or 3 × 2.

    let factoring = Factoring::new(
        2, // num_bits_first:  p is a 2-bit factor
        2, // num_bits_second: q is a 2-bit factor
        6, // target_product:  find p × q = 6
    );

Step 3 — Solve with ILPSolver

solve_reduced reduces the problem to ILP internally and solves it in one call. It returns a configuration vector for the original problem — no manual extraction needed. For small instances you can also use BruteForce, but ILPSolver scales to much larger problems.

    // Factoring reduces to ILP<i32>, so we manually reduce, solve, and extract
    let solver = ILPSolver::new();
    let reduction = ReduceTo::<ILP<i32>>::reduce_to(&factoring);
    let ilp_solution = solver.solve(reduction.target_problem()).unwrap();
    let solution = reduction.extract_solution(&ilp_solution);

Step 4 — Read and verify the factors

read_factors decodes the binary configuration back into the two integer factors.

    let (p, q) = factoring.read_factors(&solution); // decode bit assignments → integers
    println!("{} = {} × {}", factoring.target(), p, q);
    assert_eq!(p * q, 6, "Factors should multiply to 6");

6 = 3 × 2

Step 5 — Inspect the overhead

Each reduction edge carries a polynomial overhead mapping source problem sizes to target sizes. path_overheads returns the per-edge polynomials, and compose_path_overhead composes them symbolically into a single end-to-end formula.

    // Print per-edge overhead polynomials
    let edge_overheads = graph.path_overheads(&rpath);
    for (i, overhead) in edge_overheads.iter().enumerate() {
        println!("{} → {}:", rpath.steps[i], rpath.steps[i + 1]);
        for (field, poly) in &overhead.output_size {
            println!("  {} = {}", field, poly);
        }
    }

    // Compose overheads symbolically along the full path
    let composed = graph.compose_path_overhead(&rpath);
    println!("Composed (source → target):");
    for (field, poly) in &composed.output_size {
        println!("  {} = {}", field, poly);
    }

Factoring → CircuitSAT:
  num_variables = num_bits_first * num_bits_second
  num_assignments = num_bits_first * num_bits_second
CircuitSAT → SpinGlass {graph: "SimpleGraph", weight: "i32"}:
  num_spins = num_assignments
  num_interactions = num_assignments
SpinGlass {graph: "SimpleGraph", weight: "i32"} → SpinGlass {graph: "SimpleGraph", weight: "f64"}:
  num_spins = num_spins
  num_interactions = num_interactions
Composed (source → target):
  num_spins = num_bits_first * num_bits_second
  num_interactions = num_bits_first * num_bits_second

Solvers

Two solvers are available:

ILP support is enabled by default. To disable it:

[dependencies]
problemreductions = { version = "0.2", default-features = false }

JSON Resources

The library exports machine-readable metadata useful for tooling and research:

• reduction_graph.json lists all problem variants and reduction edges
• problem_schemas.json lists field definitions for each problem type

Next Steps

• Try the CLI tool to explore problems and reduction paths from your terminal
• Explore the interactive reduction graph to discover available reductions
• Read the Design guide for implementation details
• Browse the API Reference for full documentation

CLI Tool

The pred command-line tool lets you explore the reduction graph, create problem instances, solve problems, and perform reductions — all from your terminal.

Installation

Install from crates.io:

cargo install problemreductions-cli

Or build from source:

git clone https://github.com/CodingThrust/problem-reductions
cd problem-reductions
make cli    # builds target/release/pred

Verify the installation:

pred --version

ILP Backend

The default ILP backend is HiGHS. To use a different backend:

cargo install problemreductions-cli --features coin-cbc
cargo install problemreductions-cli --features scip
cargo install problemreductions-cli --no-default-features --features clarabel

Available backends: highs (default), coin-cbc, clarabel, scip, lpsolve, microlp.

Quick Start

# Create a Maximum Independent Set problem
pred create MIS --graph 0-1,1-2,2-3 -o problem.json

# Solve it (auto-reduces to ILP)
pred solve problem.json

# Or solve with brute-force
pred solve problem.json --solver brute-force

# Evaluate a specific configuration
pred evaluate problem.json --config 1,0,1,0

# Reduce to another problem type and solve via brute-force
pred reduce problem.json --to QUBO -o reduced.json
pred solve reduced.json --solver brute-force

# Pipe commands together (use - to read from stdin)
pred create MIS --graph 0-1,1-2,2-3 | pred solve -
pred create MIS --graph 0-1,1-2,2-3 | pred reduce - --to QUBO | pred solve -

Global Flags

Commands

pred list — List all problem types

Lists all registered problem types with their short aliases.

$ pred list
Registered problems: 17 types, 48 reductions, 25 variant nodes

  Problem                Aliases     Variants  Reduces to
  ─────────────────────  ──────────  ────────  ──────────
  CircuitSAT                                1           1
  Factoring                                 1           2
  ILP                                       1           1
  KColoring                                 2           3
  KSatisfiability        3SAT, KSAT         3           7
  MaxCut                                    1           1
  MaximumClique                             1           1
  MaximumIndependentSet  MIS                4          10
  MaximumMatching                           1           2
  MaximumSetPacking                         2           4
  MinimumDominatingSet                      1           1
  MinimumSetCovering                        1           1
  MinimumVertexCover     MVC                1           4
  QUBO                                      1           1
  Satisfiability         SAT                1           5
  SpinGlass                                 2           3
  TravelingSalesman      TSP                1           1

Use `pred show <problem>` to see variants, reductions, and fields.

pred show — Inspect a problem

Show variants, fields, size fields, and reductions for a problem type. Use short aliases like MIS for MaximumIndependentSet.

$ pred show MIS
MaximumIndependentSet
  Find maximum weight independent set in a graph

Variants (4):
  {graph=SimpleGraph, weight=i32}
  {graph=UnitDiskGraph, weight=i32}
  {graph=KingsSubgraph, weight=i32}
  {graph=TriangularSubgraph, weight=i32}

Fields (2):
  graph (G) -- The underlying graph G=(V,E)
  weights (Vec<W>) -- Vertex weights w: V -> R

Size fields (2):
  num_vertices
  num_edges

Reduces to (10):
  MaximumIndependentSet {graph=SimpleGraph, weight=i32} → MaximumSetPacking ...
  MaximumIndependentSet {graph=SimpleGraph, weight=i32} → MinimumVertexCover ...
  ...

Reduces from (9):
  MinimumVertexCover {graph=SimpleGraph, weight=i32} → MaximumIndependentSet ...
  Satisfiability (default) → MaximumIndependentSet {graph=SimpleGraph, weight=i32}
  ...

pred to — Explore outgoing neighbors

Explore which problems a given problem can reduce to within k hops. Each node in the tree shows its variant (graph type, weight type, etc.).

$ pred to MIS --hops 2
MaximumIndependentSet {graph=SimpleGraph, weight=i32} — 2-hop neighbors (outgoing)

MaximumIndependentSet {graph=SimpleGraph, weight=i32}
├── MaximumSetPacking {weight=i32}
│   ├── ILP (default)
│   ├── MaximumIndependentSet {graph=SimpleGraph, weight=i32}
│   └── QUBO {weight=f64}
├── MaximumIndependentSet {graph=KingsSubgraph, weight=i32}
│   └── MaximumIndependentSet {graph=SimpleGraph, weight=i32}
├── MaximumIndependentSet {graph=TriangularSubgraph, weight=i32}
│   └── MaximumIndependentSet {graph=SimpleGraph, weight=i32}
├── MinimumVertexCover {graph=SimpleGraph, weight=i32}
│   └── MaximumIndependentSet {graph=SimpleGraph, weight=i32}

5 reachable problems in 2 hops

pred from — Explore incoming neighbors

Explore which problems can reduce from (i.e., reduce into) the given problem:

$ pred from QUBO --hops 1
QUBO {weight=f64} — 1-hop neighbors (incoming)

QUBO {weight=f64}
├── MaximumIndependentSet {graph=SimpleGraph, weight=i32}
├── MinimumVertexCover {graph=SimpleGraph, weight=i32}
└── SpinGlass {graph=SimpleGraph, weight=f64}

3 reachable problems in 1 hops

pred path — Find a reduction path

Find the cheapest chain of reductions between two problems:

$ pred path MIS QUBO
Path (3 steps): MaximumIndependentSet/SimpleGraph/i32 → MaximumSetPacking/i32 → QUBO/f64

  Step 1: MaximumIndependentSet/SimpleGraph/i32 → MaximumSetPacking/i32
    num_sets = num_vertices
    universe_size = num_edges

  Step 2: MaximumSetPacking/i32 → MaximumSetPacking/f64
    num_sets = num_sets
    universe_size = universe_size

  Step 3: MaximumSetPacking/f64 → QUBO/f64
    num_vars = num_sets

  Overall:
    num_vars = num_vertices

Multi-step paths are discovered automatically:

$ pred path Factoring SpinGlass
Path (2 steps): Factoring → CircuitSAT → SpinGlass {graph: "SimpleGraph", weight: "i32"}

  Step 1: Factoring → CircuitSAT
    num_variables = num_bits_first * num_bits_second
    num_assignments = num_bits_first * num_bits_second

  Step 2: CircuitSAT → SpinGlass {graph: "SimpleGraph", weight: "i32"}
    num_spins = num_assignments
    num_interactions = num_assignments

Show all paths or save for later use with pred reduce --via:

pred path MIS QUBO --all                    # all paths
pred path MIS QUBO -o path.json             # save path for `pred reduce --via`
pred path MIS QUBO --all -o paths/          # save all paths to a folder

Use --cost to change the optimization strategy:

pred path MIS QUBO --cost minimize-steps           # default
pred path MIS QUBO --cost minimize:num_variables   # minimize a size field

Use pred show <problem> to see which size fields are available.

pred export-graph — Export the reduction graph

Export the full reduction graph as JSON:

pred export-graph                           # print to stdout
pred export-graph -o reduction_graph.json   # save to file

pred create — Create a problem instance

Construct a problem instance from CLI arguments and save as JSON:

pred create MIS --graph 0-1,1-2,2-3 -o problem.json
pred create MIS --graph 0-1,1-2,2-3 --weights 2,1,3,1 -o problem.json
pred create SAT --num-vars 3 --clauses "1,2;-1,3" -o sat.json
pred create QUBO --matrix "1,0.5;0.5,2" -o qubo.json
pred create KColoring --k 3 --graph 0-1,1-2,2-0 -o kcol.json
pred create SpinGlass --graph 0-1,1-2 -o sg.json
pred create MaxCut --graph 0-1,1-2,2-0 -o maxcut.json
pred create Factoring --target 15 --bits-m 4 --bits-n 4 -o factoring.json
pred create Factoring --target 21 --bits-m 3 --bits-n 3 -o factoring2.json

Generate random instances for graph-based problems:

pred create MIS --random --num-vertices 10 --edge-prob 0.3
pred create MIS --random --num-vertices 100 --seed 42 -o big.json
pred create MaxCut --random --num-vertices 20 --edge-prob 0.5 -o maxcut.json

Without -o, the problem JSON is printed to stdout, which can be piped to other commands:

pred create MIS --graph 0-1,1-2,2-3 | pred solve -
pred create MIS --random --num-vertices 10 | pred inspect -

The output file uses a standard wrapper format:

{
  "type": "MaximumIndependentSet",
  "variant": {"graph": "SimpleGraph", "weight": "i32"},
  "data": { ... }
}

pred evaluate — Evaluate a configuration

Evaluate a configuration against a problem instance:

$ pred evaluate problem.json --config 1,0,1,0
Valid(2)

Stdin is supported with -:

pred create MIS --graph 0-1,1-2,2-3 | pred evaluate - --config 1,0,1,0

pred inspect — Inspect a problem file

Show a summary of what's inside a problem JSON or reduction bundle:

$ pred inspect problem.json
Type: MaximumIndependentSet {graph=SimpleGraph, weight=i32}
Size: 5 vertices, 5 edges

Works with reduction bundles and stdin:

pred inspect bundle.json
pred create MIS --graph 0-1,1-2 | pred inspect -

pred reduce — Reduce a problem

Reduce a problem to a target type. Outputs a reduction bundle containing source, target, and path:

pred reduce problem.json --to QUBO -o reduced.json

Use a specific reduction path (from pred path -o). The target is inferred from the path file, so --to is not needed:

pred reduce problem.json --via path.json -o reduced.json

Stdin is supported with -:

pred create MIS --graph 0-1,1-2,2-3 | pred reduce - --to QUBO

The bundle contains everything needed to map solutions back:

{
  "source": { "type": "MaximumIndependentSet", "variant": {...}, "data": {...} },
  "target": { "type": "QUBO", "variant": {...}, "data": {...} },
  "path": [
    {"name": "MaximumIndependentSet", "variant": {"graph": "SimpleGraph", "weight": "i32"}},
    {"name": "QUBO", "variant": {"weight": "f64"}}
  ]
}

pred solve — Solve a problem

Solve a problem instance using ILP (default) or brute-force:

pred solve problem.json                         # ILP solver (default)
pred solve problem.json --solver brute-force    # brute-force solver
pred solve problem.json --timeout 30            # abort after 30 seconds

Stdin is supported with -:

pred create MIS --graph 0-1,1-2,2-3 | pred solve -
pred create MIS --graph 0-1,1-2,2-3 | pred solve - --solver brute-force

When the problem is not ILP, the solver automatically reduces it to ILP, solves, and maps the solution back. The auto-reduction is shown in the output:

$ pred solve problem.json
Problem: MaximumIndependentSet (reduced to ILP)
Solver: ilp
Solution: [1, 0, 0, 1]
Evaluation: Valid(2)

Solve a reduction bundle (from pred reduce):

$ pred solve reduced.json --solver brute-force
Source: MaximumIndependentSet
Target: QUBO (solved with brute-force)
Target solution: [0, 1, 0, 1]
Target evaluation: Valid(-2.0)
Source solution: [0, 1, 0, 1]
Source evaluation: Valid(2)

Note: The ILP solver requires a reduction path from the target problem to ILP. Some problems (e.g., QUBO, SpinGlass, MaxCut, CircuitSAT) do not have this path yet. Use --solver brute-force for these, or reduce to a problem that supports ILP first.

Shell Completions

Enable tab completion by adding one line to your shell config:

# bash (~/.bashrc)
eval "$(pred completions bash)"

# zsh (~/.zshrc)
eval "$(pred completions zsh)"

# fish (~/.config/fish/config.fish)
pred completions fish | source

If the shell argument is omitted, pred completions auto-detects your current shell.

JSON Output

All commands support -o to write JSON to a file and --json to print JSON to stdout:

pred list -o problems.json       # save to file
pred list --json                 # print JSON to stdout
pred show MIS --json             # works on any command
pred path MIS QUBO --json
pred solve problem.json --json

This is useful for scripting and piping:

pred list --json | jq '.problems[].name'
pred path MIS QUBO --json | jq '.path'

Problem Name Aliases

You can use short aliases instead of full problem names (shown in pred list):

You can also specify variants with a slash: MIS/UnitDiskGraph, SpinGlass/SimpleGraph.

If you mistype a problem name, pred will suggest the closest match:

$ pred show MaximumIndependentSe
Error: Unknown problem: MaximumIndependentSe

Did you mean: MaximumIndependentSet?

Run `pred list` to see all available problems.

MCP Server

The Model Context Protocol (MCP) is an open standard that allows AI assistants to interact with external tools and data sources. The pred CLI includes a built-in MCP server that exposes the full reduction graph, problem creation, solving, and reduction capabilities to any MCP-compatible AI assistant.

Setup

Install the pred CLI, then configure your AI assistant:

cargo install problemreductions-cli

Claude Code:

claude mcp add --scope user problemreductions -- pred mcp

Cursor / Windsurf — add to .cursor/mcp.json or ~/.codeium/windsurf/mcp_config.json:

{ "mcpServers": { "problemreductions": { "command": "pred", "args": ["mcp"] } } }

OpenCode — add to opencode.json:

{ "mcp": { "problemreductions": { "type": "local", "command": ["pred", "mcp"] } } }

Restart your AI assistant after configuration.

Walkthrough

A complete Claude Code session showing how the AI assistant uses MCP tools behind the scenes to answer your questions.

You: Create a weighted MIS problem on a 4-vertex graph with edges 0-1, 1-2, 2-3, 3-0, 0-2 and weights [1, 2, 3, 4], explain the result.

Assistant: I created a Maximum Independent Set instance on a SimpleGraph with 4 vertices, 5 edges, and integer weights [1, 2, 3, 4]. Each vertex has a weight, and the goal is to find a subset of non-adjacent vertices that maximizes total weight.

You: What can I do with this problem? Explain the result.

Assistant: This instance has 4 binary variables (one per vertex). It can be reduced to 5 other problem types: ILP, MaximumSetPacking, MinimumVertexCover, QUBO, and other MIS variants. You can solve it directly using either an ILP solver or brute-force search.

You: Check if selecting vertices 1 and 3 is a valid solution, explain the result.

Assistant: Yes! Selecting vertices 1 and 3 (configuration [0,1,0,1]) is a valid independent set — these two vertices are not adjacent. The total weight is 2 + 4 = 6.

You: Reduce this to QUBO, explain the result.

Assistant: Done. The MIS instance was transformed into a 4x4 QUBO matrix:

[-1.0, 11.0, 11.0, 11.0]
[ 0.0, -2.0, 11.0,  0.0]
[ 0.0,  0.0, -3.0, 11.0]
[ 0.0,  0.0,  0.0, -4.0]

The diagonal entries (-1, -2, -3, -4) encode vertex weights negated for minimization. The off-diagonal entries (11.0) are large penalties on edges — selecting two adjacent vertices would incur a penalty that outweighs any benefit. The reduction path is: MaximumIndependentSet → MaximumSetPacking → QUBO.

You: Now solve it through the reduction, explain the result.

Assistant: The ILP solver found the optimal solution by solving the QUBO, then mapping the result back to the original MIS:

• QUBO solution: [0,1,0,1] with objective -6.0 (minimization)
• MIS solution: vertices {1, 3} with weight 6 (maximization)

The QUBO objective of -6.0 corresponds to the MIS maximum of 6 — the reduction correctly inverts the sign. This confirms that {1, 3} is the optimal independent set.

Available Tools

The MCP server provides 10 tools organized into two categories: graph query tools for exploring the reduction graph, and instance tools for working with concrete problem instances.

Graph Query Tools

Instance Tools

Available Prompts

The server provides 7 task-oriented prompt templates:

Design

This guide covers the library internals for contributors.

Module Architecture

Problem Model

Every problem implements Problem. Optimization problems additionally implement OptimizationProblem; satisfaction problems implement SatisfactionProblem.

trait Problem: Clone {
    const NAME: &'static str;              // e.g., "MaximumIndependentSet"
    type Metric: Clone;                    // SolutionSize<W> or bool
    fn dims(&self) -> Vec<usize>;          // config space per variable
    fn evaluate(&self, config: &[usize]) -> Self::Metric;
    fn variant() -> Vec<(&'static str, &'static str)>; // e.g., [("graph", "SimpleGraph"), ("weight", "i32")]
    fn num_variables(&self) -> usize;      // default: dims().len()
}

trait OptimizationProblem: Problem<Metric = SolutionSize<Self::Value>> {
    type Value: PartialOrd + Clone;        // e.g., i32, f64
    fn direction(&self) -> Direction;      // Maximize or Minimize
}

trait SatisfactionProblem: Problem<Metric = bool> {}  // marker trait

• Problem — the base trait. Every problem declares a NAME (e.g., "MaximumIndependentSet"). The solver explores the configuration space defined by dims() and scores each configuration with evaluate(). For example, a 4-vertex MIS has dims() = [2, 2, 2, 2] (each vertex is selected or not); evaluate(&[1, 0, 1, 0]) returns Valid(2) if vertices 0 and 2 form an independent set, or Invalid if they share an edge. Each problem also provides inherent getter methods (e.g., num_vertices(), num_edges()) used by reduction overhead expressions.
• OptimizationProblem — extends Problem with a comparable Value type and a direction() (Maximize or Minimize).
• SatisfactionProblem — constrains Metric = bool: true if all constraints are satisfied, false otherwise.

Variant System

A single problem name like MaximumIndependentSet can have multiple variants — carrying weights on vertices, or defined on a restricted topology (e.g., king's subgraph). Variants form a subtype hierarchy: independent sets on king's subgraphs are a subset of independent sets on unit-disk graphs. The reduction from a more specific variant to a less specific one is a variant cast — an identity mapping where indices are preserved.

Variant types fall into three categories:

• Graph type — SimpleGraph (root), PlanarGraph, BipartiteGraph, UnitDiskGraph, KingsSubgraph, TriangularSubgraph.
• Weight type — One (unweighted), i32, f64.
• K value — e.g., K3 for 3-SAT, KN for arbitrary K.

pub trait VariantParam: 'static {
    const CATEGORY: &'static str;     // e.g., "graph", "weight", "k"
    const VALUE: &'static str;        // e.g., "SimpleGraph", "i32"
    const PARENT_VALUE: Option<&'static str>;  // None for root types
}

pub trait CastToParent: VariantParam {
    type Parent: VariantParam;
    fn cast_to_parent(&self) -> Self::Parent;
}

// Root type (no parent):
impl_variant_param!(SimpleGraph, "graph");

// K root (arbitrary K):
impl_variant_param!(KN, "k", k: None);

// Specific K with parent:
impl_variant_param!(K3, "k", parent: KN, cast: |_| KN, k: Some(3));

impl_variant_reduction!(
    MaximumIndependentSet,
    <KingsSubgraph, i32> => <UnitDiskGraph, i32>,
    fields: [num_vertices, num_edges],
    |src| MaximumIndependentSet::new(
        src.graph().cast_to_parent(), src.weights().to_vec())
);

// MaximumIndependentSet<G: VariantParam, W: VariantParam>
fn variant() -> Vec<(&'static str, &'static str)> {
    crate::variant_params![G, W]
    // e.g., MaximumIndependentSet<UnitDiskGraph, One>
    //     -> vec![("graph", "UnitDiskGraph"), ("weight", "One")]
}

Reduction Rules

A reduction requires two pieces: a result struct and a ReduceTo<T> impl.

The result struct holds the target problem and the logic to map solutions back:

#[derive(Debug, Clone)]
pub struct ReductionISToVC<W> {
    target: MinimumVertexCover<SimpleGraph, W>,
}

impl<W: WeightElement + VariantParam> ReductionResult for ReductionISToVC<W> {
    type Source = MaximumIndependentSet<SimpleGraph, W>;
    type Target = MinimumVertexCover<SimpleGraph, W>;

    fn target_problem(&self) -> &Self::Target { &self.target }
    fn extract_solution(&self, target_sol: &[usize]) -> Vec<usize> {
        target_sol.iter().map(|&x| 1 - x).collect()  // complement
    }
}

The #[reduction] attribute on the ReduceTo<T> impl registers the reduction in the global registry (via inventory):

#[reduction(overhead = {
    num_vertices = "num_vertices",
    num_edges = "num_edges",
})]
impl ReduceTo<MinimumVertexCover<SimpleGraph, i32>>
    for MaximumIndependentSet<SimpleGraph, i32>
{
    type Result = ReductionISToVC<i32>;
    fn reduce_to(&self) -> Self::Result { /* ... */ }
}

inventory::submit! {
    ReductionEntry {
        source_name: "MaximumIndependentSet",
        target_name: "MinimumVertexCover",
        source_variant_fn: || <MaximumIndependentSet<SimpleGraph, i32> as Problem>::variant(),
        target_variant_fn: || <MinimumVertexCover<SimpleGraph, i32> as Problem>::variant(),
        overhead_fn: || ReductionOverhead {
            output_size: vec![
                ("num_vertices", Expr::Var("num_vertices")),
                ("num_edges", Expr::Var("num_edges")),
            ],
        },
        module_path: module_path!(),
        reduce_fn: |src: &dyn Any| -> Box<dyn DynReductionResult> {
            let src = src.downcast_ref::<MaximumIndependentSet<SimpleGraph, i32>>().unwrap();
            Box::new(ReduceTo::<MinimumVertexCover<SimpleGraph, i32>>::reduce_to(src))
        },
    }
}

Reduction Graph

ReductionGraph::new() iterates all registered ReductionEntry items (via inventory) and builds a variant-level directed graph:

• Nodes are unique (problem_name, variant) pairs — e.g., ("MaximumIndependentSet", {graph: "KingsSubgraph", weight: "i32"}).
• Edges come exclusively from #[reduction] registrations — both cross-problem reductions and variant casts. There are no auto-generated edges.

Exported files:

• reduction_graph.json — all problem variants and reduction edges
• problem_schemas.json — field definitions for each problem type

Regenerate with cargo run --example export_graph and cargo run --example export_schemas.

Path finding

All path-finding operates on exact variant nodes. Use ReductionGraph::variant_to_map(&T::variant()) to convert a Problem::variant() into the required BTreeMap<String, String>.

Use find_cheapest_path with MinimizeSteps for fewest-hops search.

The PathCostFn trait (used by find_cheapest_path) computes edge cost from overhead and current problem size:

CustomCost wraps a closure that receives the edge's ReductionOverhead (polynomial mapping from input to output size fields) and the current ProblemSize (accumulated field values at that point in the path), and returns an f64 edge cost. Dijkstra minimizes the total cost along the path.

Example: Finding a path from MIS{KingsSubgraph, i32} to VC{SimpleGraph, i32}:

MIS{KingsSubgraph,i32} -> MIS{UnitDiskGraph,i32} -> MIS{SimpleGraph,i32} -> VC{SimpleGraph,i32}
     variant cast              variant cast                reduction

Executable paths

Convert a ReductionPath into a typed ExecutablePath<S, T> via make_executable(), then call reduce():

// find_cheapest_path returns a ReductionPath (list of variant node IDs)
let rpath = graph.find_cheapest_path("Factoring", &src_var,
    "SpinGlass", &dst_var, &ProblemSize::new(vec![]), &MinimizeSteps).unwrap();

// make_executable converts it into a typed, callable chain
let path = graph.make_executable::<Factoring, SpinGlass<SimpleGraph, f64>>(&rpath).unwrap();

// reduce() applies each step, returning a ChainedReduction
let reduction = path.reduce(&factoring_instance);
let target: &SpinGlass<SimpleGraph, f64> = reduction.target_problem();
let solution: Vec<usize> = reduction.extract_solution(&target_solution);

ExecutablePath holds a type-erased ReduceFn per edge. reduce() applies them sequentially, producing a ChainedReduction that stores each intermediate result. extract_solution maps the final solution back through the chain in reverse order.

For full type control, you can also chain ReduceTo::reduce_to() calls manually at each step.

#[reduction(overhead = {
    num_vars = "num_vertices + num_edges",
    num_clauses = "3 * num_edges",
})]
impl ReduceTo<Target> for Source { ... }

Input:  ProblemSize { num_vertices: 10, num_edges: 15 }
Output: ProblemSize { num_vars: 25, num_clauses: 45 }

Solvers

Solvers implement the Solver trait:

pub trait Solver {
    fn find_best<P: OptimizationProblem>(&self, problem: &P) -> Option<Vec<usize>>;
    fn find_satisfying<P: Problem<Metric = bool>>(&self, problem: &P) -> Option<Vec<usize>>;
}

JSON Serialization

All problem types support JSON serialization via serde:

use problemreductions::io::{to_json, from_json};

let json: String = to_json(&problem)?;
let restored: MaximumIndependentSet<SimpleGraph, i32> = from_json(&json)?;

Contributing

See Call for Contributions for the recommended issue-based workflow (no coding required).

API Reference

Full API documentation is auto-generated from source code via rustdoc.

Browse the API →

If not redirected automatically, run make doc to generate the API docs.

Complexity & Overhead Correctness Review

Systematic review of declare_variants! complexity expressions and #[reduction(overhead)] formulas. New reviews should be appended to the appropriate table. See Issue #107 for methodology.

Review result: PASS (correct), FAIL (wrong — needs fix), UNVERIFIED (not yet reviewed).

Models (Variant Complexity)

The complexity field represents the worst-case time complexity of the best known algorithm for each problem variant.

Rules (Reduction Overhead)

The overhead formula describes how target problem size relates to source problem size.