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

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
cargo build -p problemreductions-cli --release   # builds target/release/pred
cargo install --path problemreductions-cli       # optional: installs `pred` to ~/.cargo/bin

Verify the installation:

pred --version

For a workspace-local run without installing globally, use:

cargo run -p problemreductions-cli --bin 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

# Create a weighted instance (variant auto-upgrades to i32)
pred create MIS --graph 0-1,1-2,2-3 --weights 3,1,2,1 -o weighted.json

# Create a Steiner Tree instance
pred create SteinerTree --graph 0-1,0-3,1-2,1-3,2-3,2-4,3-4 --edge-weights 2,5,2,1,5,6,1 --terminals 0,2,4 -o steiner.json

# Create a Length-Bounded Disjoint Paths instance
pred create LengthBoundedDisjointPaths --graph 0-1,1-6,0-2,2-3,3-6,0-4,4-5,5-6 --source 0 --sink 6 --bound 4 -o lbdp.json

# Create a Consecutive Block Minimization instance (alias: CBM)
pred create CBM --matrix '[[true,false,true],[false,true,true]]' --bound 2 -o cbm.json

# CBM currently needs the brute-force solver
pred solve cbm.json --solver brute-force

# Or start from a canonical model example
pred create --example MIS/SimpleGraph/i32 -o example.json

# Or from a canonical rule example
pred create --example MVC/SimpleGraph/i32 --to MIS/SimpleGraph/i32 -o example.json

# Inspect what's inside a problem file
pred inspect problem.json

# Inspect the new path problem
pred inspect lbdp.json

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

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

# LengthBoundedDisjointPaths currently needs brute-force
pred solve lbdp.json --solver brute-force

# Evaluate a specific configuration (shows the aggregate value, e.g. Max(2) or Min(None))
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 -   # when an ILP reduction path exists
pred create StringToStringCorrection --source-string "0,1,2,3,1,0" --target-string "0,1,3,2,1" --bound 2 | pred solve - --solver brute-force
pred create MIS --graph 0-1,1-2,2-3 | pred reduce - --to QUBO | pred solve -

Note: When you provide --weights with non-unit values (e.g., 3,1,2,1), the variant is automatically upgraded from the default unit-weight (One) to i32. You can also specify the weighted variant explicitly: pred create MIS/SimpleGraph/i32 --graph 0-1 --weights 3,1.

Global Flags

Commands

pred list — List all problem types

Lists all registered problem types with their short aliases.

{{#include generated/pred-list.txt}}

pred show — Inspect a problem

Show fields, size fields, and reductions for a problem's default variant. Use short aliases like MIS for MaximumIndependentSet. Use pred to or pred from for variant-level neighborhood exploration.

{{#include generated/pred-show-mis.txt}}

pred to — Explore incoming neighbors

Explore which problems can reduce to the given problem within k hops:

{{#include generated/pred-to-mis.txt}}

pred from — Explore outgoing neighbors

Explore which problems the given problem can reduce to, starting from it:

{{#include generated/pred-from-qubo.txt}}

pred path — Find a reduction path

Find the cheapest chain of reductions between two problems:

{{#include generated/pred-path-mis-qubo.txt}}

Multi-step paths are discovered automatically:

{{#include generated/pred-path-factoring-spinglass.txt}}

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

pred path MIS QUBO --all                    # all paths (up to 20)
pred path MIS QUBO --all --max-paths 50     # increase limit
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

When using --all, the output is capped at --max-paths (default: 20). If more paths exist, the output indicates truncation.

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 --example MIS/SimpleGraph/i32 -o model.json
pred create --example MVC/SimpleGraph/i32 --to MIS/SimpleGraph/i32 -o problem.json
pred create --example MVC/SimpleGraph/i32 --to MIS/SimpleGraph/i32 --example-side target -o target.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 CBM --matrix '[[true,false,true],[false,true,true]]' --bound 2 -o cbm.json
pred create KColoring --k 3 --graph 0-1,1-2,2-0 -o kcol.json
pred create KthBestSpanningTree --graph 0-1,0-2,1-2 --edge-weights 2,3,1 --k 1 --bound 3 -o kth.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 MinMaxMulticenter --graph 0-1,1-2,2-3 --weights 1,1,1,1 --edge-weights 1,1,1 --k 2 -o pcenter.json
pred create ShortestWeightConstrainedPath --graph 0-1,0-2,1-3,2-3,2-4,3-5,4-5,1-4 --edge-lengths 2,4,3,1,5,4,2,6 --edge-weights 5,1,2,3,2,3,1,1 --source-vertex 0 --target-vertex 5 --weight-bound 8 -o swcp.json
pred create RectilinearPictureCompression --matrix "1,1,0,0;1,1,0,0;0,0,1,1;0,0,1,1" --k 2 -o rpc.json
pred solve rpc.json --solver brute-force
pred create MinimumMultiwayCut --graph 0-1,1-2,2-3,3-0 --terminals 0,2 --edge-weights 3,1,2,4 -o mmc.json
pred create SteinerTree --graph 0-1,0-3,1-2,1-3,2-3,2-4,3-4 --edge-weights 2,5,2,1,5,6,1 --terminals 0,2,4 -o steiner.json
pred create UndirectedTwoCommodityIntegralFlow --graph 0-2,1-2,2-3 --capacities 1,1,2 --source-1 0 --sink-1 3 --source-2 1 --sink-2 3 --requirement-1 1 --requirement-2 1 -o utcif.json
pred create LengthBoundedDisjointPaths --graph 0-1,1-6,0-2,2-3,3-6,0-4,4-5,5-6 --source 0 --sink 6 --bound 4 -o lbdp.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
pred create X3C --universe 9 --sets "0,1,2;0,2,4;3,4,5;3,5,7;6,7,8;1,4,6;2,5,8" -o x3c.json
pred create MinimumCardinalityKey --num-attributes 6 --dependencies "0,1>2;0,2>3;1,3>4;2,4>5" -o mck.json
pred create MinimumTardinessSequencing --n 5 --deadlines 5,5,5,3,3 --precedence-pairs "0>3,1>3,1>4,2>4" -o mts.json
pred create SchedulingWithIndividualDeadlines --n 7 --deadlines 2,1,2,2,3,3,2 --num-processors 3 --precedence-pairs "0>3,1>3,1>4,2>4,2>5" -o swid.json
pred solve swid.json --solver brute-force
pred create SequencingToMinimizeWeightedCompletionTime --lengths 2,1,3,1,2 --weights 3,5,1,4,2 --precedence-pairs "0>2,1>4" -o stmwct.json
pred create StringToStringCorrection --source-string "0,1,2,3,1,0" --target-string "0,1,3,2,1" --bound 2 | pred solve - --solver brute-force
pred create StrongConnectivityAugmentation --arcs "0>1,1>2,2>0,3>4,4>3,2>3,4>5,5>3" --candidate-arcs "3>0:5,3>1:3,3>2:4,4>0:6,4>1:2,4>2:7,5>0:4,5>1:3,5>2:1,0>3:8,0>4:3,0>5:2,1>3:6,1>4:4,1>5:5,2>4:3,2>5:7,1>0:2" --bound 1 -o sca.json

For LengthBoundedDisjointPaths, the CLI flag --bound maps to the JSON field max_length.

For ConsecutiveBlockMinimization, the --matrix flag expects a JSON 2D bool array such as '[[true,false,true],[false,true,true]]'. The example above shows the accepted shape, and solving CBM instances currently requires --solver brute-force.

For problem-specific create help, run pred create <PROBLEM> with no additional flags. The generic pred create --help output lists all flags across all problem types.

Canonical examples are useful when you want a known-good instance from the paper/example database. For model examples, pred create --example <PROBLEM_SPEC> emits the canonical instance for that graph node. For rule examples, pred create --example <SOURCE_SPEC> --to <TARGET_SPEC> emits the source instance by default; use --example-side target to emit the reduction target instance instead.

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 -   # when an ILP reduction path exists
pred create StringToStringCorrection --source-string "0,1,2,3,1,0" --target-string "0,1,3,2,1" --bound 2 | pred solve - --solver brute-force
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": { ... }
}

Example: Bounded Component Spanning Forest

BoundedComponentSpanningForest uses one component label per vertex in the evaluation config. If the graph has n vertices and limit k, then --config expects n comma-separated integers in 0..k-1.

pred create BoundedComponentSpanningForest \
  --graph 0-1,1-2,2-3,3-4,4-5,5-6,6-7,0-7,1-5,2-6 \
  --weights 2,3,1,2,3,1,2,1 \
  --k 3 \
  --bound 6 \
  -o bcsf.json

pred evaluate bcsf.json --config 0,0,1,1,1,2,2,0
pred solve bcsf.json --solver brute-force

The brute-force solver is required here because this model does not yet have an ILP reduction path.

pred evaluate — Evaluate a configuration

Evaluate a configuration against a problem instance:

{{#include generated/pred-evaluate.txt}}

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), brute-force, or the customized solver:

pred solve problem.json                         # ILP solver (default)
pred solve problem.json --solver brute-force    # brute-force solver
pred solve problem.json --solver customized     # structure-exploiting exact 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
pred create MinMaxMulticenter --graph 0-1,1-2,2-3 --weights 1,1,1,1 --edge-weights 1,1,1 --k 2 | pred solve - --solver brute-force
pred create TwoDimensionalConsecutiveSets --alphabet-size 6 --sets "0,1,2;3,4,5;1,3;2,4;0,5" | pred solve - --solver brute-force

Output is JSON. When the problem is not ILP, the solver automatically reduces it to ILP, solves, and maps the solution back:

{{#include generated/pred-solve-ilp.txt}}

Solve a reduction bundle (from pred reduce):

{{#include generated/pred-solve-bundle.txt}}

Note: The ILP solver requires a reduction path from the target problem to ILP. Some problems do not currently have one. Examples include BoundedComponentSpanningForest, LengthBoundedDisjointPaths, MinimumCardinalityKey, QUBO, SpinGlass, MaxCut, CircuitSAT, MinMaxMulticenter, and MultiprocessorScheduling. Use pred solve <file> --solver brute-force for these, or reduce to a problem that supports ILP first. For other problems, use pred path <PROBLEM> ILP to check whether an ILP reduction path exists.

For example, the canonical Minimum Cardinality Key instance can be created and solved with:

pred create MinimumCardinalityKey --num-attributes 6 --dependencies "0,1>2;0,2>3;1,3>4;2,4>5" -o mck.json
pred solve mck.json --solver brute-force

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 '.variants[].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):

{{#include generated/pred-aliases.txt}}

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

When a bare name (no slash) is used in commands like path, to, from, create, or reduce, it resolves to the declared default variant for that problem type. For example, MIS resolves to MaximumIndependentSet/SimpleGraph/One.

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

{{#include generated/pred-show-typo.txt}}

AI Agent Skills

AI coding assistants (Claude Code, OpenCode, Codex) can call pred CLI commands directly and use interactive skills to work with the reduction graph.

Quick Start

Paste into Claude Code or Codex:

1. Clone https://github.com/CodingThrust/problem-reductions,
2. Build the pred CLI with `make cli` in the root directory,
3.1 Run `/find-solver` skill to help me find a solver for my scheduling problem.
3.2 Run `/find-problem` skill to help me find problems that my QUBO solver can solve.
3.3 Run `/propose` skill to help me propose a new problem or reduction to the project.

The prompt 3.1 is for users who have a real-world problem and need help finding a solver for it. The prompt 3.2 is for users who have a solver and need help finding problems that it can solve. The prompt 3.3 is for contributors who want to propose a new problem or reduction rule to the project.

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

cargo add problemreductions

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 Max(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);

{{#include generated/factoring-path.txt}}

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");

{{#include generated/factoring-result.txt}}

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);
    }

{{#include generated/factoring-overhead.txt}}

Solvers

Three solvers are available:

ILP support is enabled by default. To disable it:

cargo add problemreductions --no-default-features

JSON Resources

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

These files are generated when you build the docs locally.

• 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

Design

This guide covers the library internals for contributors.

Module Architecture

Problem Model

Every problem implements Problem. The associated Value type is the per-configuration aggregate returned by evaluate(). Solvers fold these values across the configuration space, and witness-capable aggregates can also recover representative configurations.

trait Problem: Clone {
    const NAME: &'static str;              // e.g., "MaximumIndependentSet"
    type Value: Clone;                     // e.g., Max<i32>, Or, Sum<i32>
    fn dims(&self) -> Vec<usize>;          // config space per variable
    fn evaluate(&self, config: &[usize]) -> Self::Value;
    fn variant() -> Vec<(&'static str, &'static str)>; // e.g., [("graph", "SimpleGraph"), ("weight", "i32")]
    fn num_variables(&self) -> usize;      // default: dims().len()
    fn problem_type() -> ProblemType;      // default: registry lookup by NAME
}

• 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 Max(Some(2)) if vertices 0 and 2 form an independent set, or Max(None) if they share an edge. Each problem also provides inherent getter methods (e.g., num_vertices(), num_edges()) used by reduction overhead expressions.
• Witness-capable objective problems — typically use Max<V>, Min<V>, or Extremum<V> as Value.
• Witness-capable feasibility problems — typically use Or.
• Aggregate-only problems — use fold values such as Sum<W> or And; these solve to a value but do not admit representative witness configurations.
• Common aggregate wrappers — Max<V>, Min<V>, Sum<W>, Or, And, Extremum<V>, ExtremumSense.

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

These JSON assets are generated during make doc, make mdbook, and make paper; they are build artifacts, not committed source files. Generate them manually with cargo run --example export_graph and cargo run --example export_schemas when you need the raw exports locally.

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 solve<P>(&self, problem: &P) -> P::Value
    where
        P: Problem,
        P::Value: Aggregate;
}

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.

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: