Problem Reductions

Problem Reductions is a Rust library and command-line tool for NP-hard problems and the reductions between them. Each problem is a model with a configuration space and an objective. Each reduction is a registered rule that maps an instance of one problem to an instance of another and maps solutions back. Searching the reduction graph yields a route from a problem to a solver, such as integer linear programming, with recovery of a solution to the original instance. The catalog currently holds:

204 problem families · 246 concrete variants · 301 directed reductions

• Atlas: every problem variant and reduction, with schemas and overheads
• Paper: definitions, constructions, and proofs
• Rust API: generated from source

This guide covers the pred CLI, the agent skills shipped with the repository, and the Rust library. Every page has a Markdown link for reading without a browser; the Markdown index lists all pages.

Cite

@misc{pan2026problemreductionsscaleagentic,
  title         = {Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems},
  author        = {Xi-Wei Pan and Shi-Wen An and Jin-Guo Liu},
  year          = {2026},
  eprint        = {2604.11535},
  archivePrefix = {arXiv},
  primaryClass  = {cs.AI},
  url           = {https://arxiv.org/abs/2604.11535},
}

Research scope

The long-term goal is autonomous discovery of new reduction rules. Today the repository provides executable models, registered reductions, solver routing, and agent workflows for proposals, implementation, and review. A rule needs a mathematical argument as well as tests; passing finite examples does not establish a general proof.

Quick start

Install

cargo install problemreductions-cli
pred --version

Rust and a native build toolchain are required. ILP solving uses the bundled HiGHS backend.

The published crate may lag behind the catalog on this site. To build the current checkout:

git clone https://github.com/CodingThrust/problem-reductions
cd problem-reductions
cargo install --path problemreductions-cli

First solve

pred create MIS --graph 0-1,1-2,2-3,3-4,4-0 -o cycle.json
pred solve cycle.json
pred evaluate cycle.json --config '[true,false,true,false,false]'

MIS is Maximum Independent Set: select as many pairwise non-adjacent vertices as possible. The graph is a cycle on five vertices. solve executes the registered ILP pipeline and maps the solution back, reporting Max(2) with a configuration such as [true, false, true, false, false]. evaluate scores a configuration of your own against the same instance. Several optimal configurations exist, so the solver's choice may differ from yours.

Terminal session

A recording of the real CLI: discover a route, transform the instance, solve, and check the result.

Open the player · Download the cast

pred path MIS ILP --json -o paths.json
python3 -c 'import json; print(json.dumps(json.load(open("paths.json"))["paths"][0]))' > path.json
pred create MIS --graph 0-1,1-2,2-3,3-4,4-0 -o cycle.json
pred reduce cycle.json --via path.json -o reduced.json
pred solve reduced.json
pred evaluate cycle.json --config '[true,false,true,false,false]'
pred solve cycle.json

path.json contains one explicitly selected route from the returned path set. reduced.json keeps the source instance and that route, so solving the bundle recovers a source solution. The final command solves the original file through its registered ILP pipeline. Both solves and the independent evaluation return Max(2); optimal solutions may differ.

Command reference

Every command accepts --json for structured output, -o FILE to save JSON, and -q to silence informational messages. pred <command> --help lists all flags; this page shows one example per command.

Catalog

pred list
pred show MIS
pred list --rules

list reports every problem with its aliases, variants, and reduction counts. show describes the resolved variant, its parameter fields, input schema, and incoming and outgoing reductions. Read that schema before constructing an instance.

MaximumIndependentSet/SimpleGraph/One
  Find maximum weight independent set in a graph
  Best Known Complexity: O(1.1996^num_vertices)

Inputs (2):
  graph (Vec<(usize,usize)>)
  num_vertices (usize) [optional]

Parameters (2):
  num_edges
  num_vertices

Outgoing reductions (6):
  → MaximumIndependentSet/TriangularSubgraph/i64  (num_edges <= 108 * num_vertices + 108 * num_vertices^2, num_vertices <= 36 * num_vertices + 36 * num_vertices^2)
  → MaximumSetPacking/One  (num_sets <= num_vertices, universe_size <= num_edges)
  → MaximumIndependentSet/SimpleGraph/i64  (num_edges = num_edges, num_vertices = num_vertices)
  → DecisionMaximumIndependentSet/SimpleGraph/One  (num_edges = num_edges, num_vertices = num_vertices)
  → MaximumClique/SimpleGraph/One  (num_edges = -1 * num_edges + num_vertices * (-1 + num_vertices) * 2^-1, num_vertices = num_vertices)
  → MaximumIndependentSet/KingsSubgraph/One  (num_edges <= 48 + 64 * num_vertices^2 + 128 * num_vertices, num_vertices <= 12 + 16 * num_vertices^2 + 32 * num_vertices)

Incoming reductions (6):
  LongestCommonSubsequence →  (num_edges <= cross_frequency_product^2, num_vertices <= cross_frequency_product)
  MaximumClique/SimpleGraph/One →  (num_edges = -1 * num_edges + num_vertices * (-1 + num_vertices) * 2^-1, num_vertices = num_vertices)
  Satisfiability →  (num_edges <= num_literals^2, num_vertices <= num_literals)
  MaximumSetPacking/One →  (num_edges <= num_sets^2, num_vertices <= num_sets)
  MaximumIndependentSet/UnitDiskGraph/One →  (num_edges = num_edges, num_vertices = num_vertices)
  DecisionMaximumIndependentSet/SimpleGraph/One →  (num_edges = num_edges, num_vertices = num_vertices)

Names and variants

pred show MIS/SimpleGraph/i64
pred path MIS/SimpleGraph/i64 ILP/bool

Aliases such as MIS resolve to full names, and a bare name selects the declared default variant: MIS is MaximumIndependentSet/SimpleGraph/One. Slash-separated parameters select graph, weight, or other variant values. One means unit weights; passing non-unit --weights to create upgrades a default instance to i64. Name the exact variant when a reproducible endpoint matters.

Paths

pred path MIS ILP
pred path MIS QUBO --limit 50
pred path MIS QUBO --json -o paths.json
pred from MIS --hops 2
pred to QUBO

path enumerates witness-capable simple routes between exact endpoints, without ranking. --limit accepts 1 through 999, or all for 999; the default is 20. JSON output contains paths and truncated. from and to explore outgoing and incoming neighbors.

Found 3 paths from Factoring to SpinGlass:

--- Path 1 ---
Path (2 steps): Factoring → CircuitSAT → SpinGlass/SimpleGraph/i64

  Step 1: Factoring → CircuitSAT
    num_assignment_outputs unavailable: the exact target parameter is not represented by this reduction's symbolic transform
    num_assignments <= 2 + 2 * (num_bits_first + num_bits_second) + 6 * num_bits_first * num_bits_second
    num_expression_nodes unavailable: the exact target parameter is not represented by this reduction's symbolic transform
    num_variables <= 1 + 2 * (num_bits_first + num_bits_second) + 6 * num_bits_first * num_bits_second

  Step 2: CircuitSAT → SpinGlass/SimpleGraph/i64
    num_interactions <= num_assignment_outputs + 6 * num_expression_nodes
    num_spins <= num_variables + 3 * num_expression_nodes

  Overall:
    num_interactions unavailable: cannot compose reduction step 2 (CircuitSAT -> SpinGlass): reduction `Factoring -> SpinGlass` target field `num_spins` is missing composition inputs ["num_expression_nodes"]
    num_spins unavailable: cannot compose reduction step 2 (CircuitSAT -> SpinGlass): reduction `Factoring -> SpinGlass` target field `num_spins` is missing composition inputs ["num_expression_nodes"]

--- Path 2 ---
Path (5 steps): Factoring → CircuitSAT → Satisfiability → Maximum2Satisfiability → MaxCut/SimpleGraph/i64 → SpinGlass/SimpleGraph/i64

  Step 1: Factoring → CircuitSAT
    num_assignment_outputs unavailable: the exact target parameter is not represented by this reduction's symbolic transform
    num_assignments <= 2 + 2 * (num_bits_first + num_bits_second) + 6 * num_bits_first * num_bits_second
    num_expression_nodes unavailable: the exact target parameter is not represented by this reduction's symbolic transform
    num_variables <= 1 + 2 * (num_bits_first + num_bits_second) + 6 * num_bits_first * num_bits_second

  Step 2: CircuitSAT → Satisfiability
    num_clauses unavailable: the exact Tseitin clause count is specific to this reduction and is not a CircuitSAT parameter
    num_literals unavailable: the exact target parameter is not represented by this reduction's symbolic transform
    num_vars unavailable: the exact Tseitin variable count is specific to this reduction and is not a CircuitSAT parameter

  Step 3: Satisfiability → Maximum2Satisfiability
    num_clauses <= 10 * (num_literals + 3 * num_clauses)
    num_vars <= num_vars + 2 * num_literals + 4 * num_clauses

  Step 4: Maximum2Satisfiability → MaxCut/SimpleGraph/i64
    num_edges <= (1 + num_vars)^2
    num_vertices <= 1 + num_vars

  Step 5: MaxCut/SimpleGraph/i64 → SpinGlass/SimpleGraph/i64
    num_interactions = num_edges
    num_spins = num_vertices

  Overall:
    num_interactions unavailable: reduction step 2 (CircuitSAT -> Satisfiability) has no symbolic parameter transform
    num_spins unavailable: reduction step 2 (CircuitSAT -> Satisfiability) has no symbolic parameter transform

--- Path 3 ---
Path (5 steps): Factoring → CircuitSAT → Satisfiability → NAESatisfiability → MaxCut/SimpleGraph/i64 → SpinGlass/SimpleGraph/i64

  Step 1: Factoring → CircuitSAT
    num_assignment_outputs unavailable: the exact target parameter is not represented by this reduction's symbolic transform
    num_assignments <= 2 + 2 * (num_bits_first + num_bits_second) + 6 * num_bits_first * num_bits_second
    num_expression_nodes unavailable: the exact target parameter is not represented by this reduction's symbolic transform
    num_variables <= 1 + 2 * (num_bits_first + num_bits_second) + 6 * num_bits_first * num_bits_second

  Step 2: CircuitSAT → Satisfiability
    num_clauses unavailable: the exact Tseitin clause count is specific to this reduction and is not a CircuitSAT parameter
    num_literals unavailable: the exact target parameter is not represented by this reduction's symbolic transform
    num_vars unavailable: the exact Tseitin variable count is specific to this reduction and is not a CircuitSAT parameter

  Step 3: Satisfiability → NAESatisfiability
    num_clauses = num_clauses
    num_literal_pairs unavailable: the exact target parameter is not represented by this reduction's symbolic transform
    num_literals = num_clauses + num_literals
    num_vars = 1 + num_vars

  Step 4: NAESatisfiability → MaxCut/SimpleGraph/i64
    num_edges <= num_vars + -7 * num_clauses + 4 * num_literals
    num_vertices <= 2 * (num_literals + num_vars + -2 * num_clauses)

  Step 5: MaxCut/SimpleGraph/i64 → SpinGlass/SimpleGraph/i64
    num_interactions = num_edges
    num_spins = num_vertices

  Overall:
    num_interactions unavailable: reduction step 2 (CircuitSAT -> Satisfiability) has no symbolic parameter transform
    num_spins unavailable: reduction step 2 (CircuitSAT -> Satisfiability) has no symbolic parameter transform

Parameter transforms declare exact equalities, upper bounds, or unavailable relations. A discovered route does not imply the target is cheap to solve; inspect the constructed target on representative instances.

Create

pred create MIS --graph 0-1,1-2,2-3 -o problem.json
pred create MIS/SimpleGraph/i64 --graph 0-1,1-2,2-3 --weights 2,1,3,1 -o weighted.json
pred create --example MVC/SimpleGraph/i64 --to MIS/SimpleGraph/i64 -o source.json
pred create MIS --random --num-vertices 10 --edge-prob 0.3 --seed 42 -o random.json

Flags follow the schema field names in kebab-case: universe_size becomes --universe-size. Vertices use zero-based indices and --graph is a comma-separated edge list. --example loads a canonical model fixture, or with --to the source side of a documented reduction example (--example-side target for the other side). --random generates a graph instance; save the JSON so the instance can be reproduced.

Other input structures:

pred create SAT --num-vars 3 --clauses '1,2;-1,3' -o sat.json          # signed one-based literals; ';' separates clauses
pred create QUBO --matrix '1,0.5;0.5,2' -o qubo.json                    # ';' separates rows
pred create X3C --universe-size 6 --subsets '0,1,2;3,4,5;0,3,4' -o x3c.json
pred create Factoring --target 6 --m 2 --n 2 -o factoring.json

Inspect and evaluate

pred inspect problem.json
pred evaluate problem.json --config '[true,false,true,false]'
pred create MIS --graph 0-1,1-2,2-3 | pred evaluate - --config '[true,false,true,false]'

inspect reports the resolved variant and sizes of a problem file or reduction bundle. evaluate scores one configuration: selecting vertices 0 and 2 returns Max(2), while selecting adjacent vertices returns Max(None). Configurations follow each problem's variable domains and are not always binary. - reads from stdin.

For a problem file, JSON inspection includes parameter_values, the model's actual named instance parameters. These are separate from the parameters list of parameter names.

Reduce

pred path MIS QUBO --json -o paths.json
python3 -c 'import json; print(json.dumps(json.load(open("paths.json"))["paths"][0]))' > path.json
pred reduce problem.json --via path.json -o reduced.json
pred extract reduced.json --config '[1,0,1,0]'

The bundle contains the source instance, the target instance, and the variant-level path; keep it whole to preserve solution recovery. --via replays one route extracted from the paths envelope, whose source variant must match the input. extract maps a target-space configuration back to the source.

Solve

pred solve problem.json
pred solve problem.json --solver brute-force
pred solve reduced.json --timeout 30 --json

Default dispatch tries registered customized, ILP, then brute-force capabilities in that order. pred inspect lists the capabilities available for the exact variant. Solving a bundle solves its target and maps the result back; every successful solve returns a solution. A discovered path does not by itself provide a registered solver. Evaluate the returned solution on the original instance to verify its value.

JSON and pipes

pred create MIS --graph 0-1,1-2,2-3 | pred reduce - --via path.json | pred solve - --json
pred export-graph -o reduction_graph.json

Check the exit status before consuming a result, and enable set -o pipefail in scripts. Keep type and variant with each instance; an alias alone does not identify an exact endpoint. The site publishes reduction_graph.json and problem_schemas.json from the same registry; the local export-graph describes the installed version.

Shell completions

eval "$(pred completions bash)"        # ~/.bashrc
eval "$(pred completions zsh)"         # ~/.zshrc
pred completions fish | source         # ~/.config/fish/config.fish

Without an argument, pred completions detects the current shell.

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.

For exact variants and structured output, use CLI path queries.

Skills

Skills are task procedures under .claude/skills/<name>/SKILL.md in the repository. An agent reads one and follows it, using the pred CLI for current model, variant, and path data. They work with Claude Code as slash commands (/find-solver) and with any agent that can read files.

Setup

git clone https://github.com/CodingThrust/problem-reductions
cd problem-reductions
make cli

This installs pred into Cargo's binary directory. Give the agent this context:

Work in this repository. Read AGENTS.md and .claude/CLAUDE.md.
Use the built pred CLI to inspect current models, variants, and paths.
Read the SKILL.md for the task before following its workflow.
Report the exact model variant, commands, results, and unresolved assumptions.

Every skill is invoked the same way. Name the skill, then describe the task:

Read .claude/skills/find-solver/SKILL.md and follow it.
My problem: [inputs, constraints, and objective].
Typical size: [counts and ranges].

Use the atlas

Ask the agent to construct a small instance, solve it, and evaluate the recovered configuration on the original problem before scaling up. A solver for a target handles sources that reduce to it; a route in the other direction establishes nothing.

Contribute

For a rule, distinguish a construction supported by literature from a new conjecture, and record proof gaps and counterexamples explicitly.

Maintain

The corresponding make targets run in a configured maintainer checkout:

make run-issue N=42      # implement one issue
make run-pipeline        # pick the next Ready issue
make run-review N=570    # review one pull request

A passing test suite is evidence for the tested instances, not a proof for all inputs. Keep the mathematical argument, the constructor and adversary checks, closed-loop tests, and review findings with the work.

Reading without a browser

The Markdown index lists every page of this guide with code includes expanded. reduction_graph.json and problem_schemas.json provide the registry as structured data.

Authorship

Contributors of ten non-trivial reduction rules are added to the author list of the paper. The software is MIT licensed.

Getting started

cargo add problemreductions

The library includes the HiGHS ILP backend.

Solve a small instance

use problemreductions::prelude::*;

fn main() {
    let problem = MaximumSetPacking::<i64>::new(vec![
        vec![0, 1], vec![1, 2], vec![2, 3], vec![4, 5],
    ]);
    let solver = BruteForce::new();
    let solution = solver.solve(&problem).unwrap().unwrap();
    println!("{:?}: {}", solution, problem.evaluate(&solution).unwrap());
}

The optimal packing selects sets 0, 2, and 3: the witness is [true, false, true, true] and evaluates to Max(3). Problem::evaluate scores a configuration; BruteForce enumerates the configuration space, so keep exhaustive examples small.

Apply a reduction

Reduce the same instance to binary ILP, solve the target, and recover the original configuration:

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

fn main() {
    let problem = MaximumSetPacking::<i64>::new(vec![
        vec![0, 1], vec![1, 2], vec![2, 3], vec![4, 5],
    ]);
    let reduction = ReduceTo::<ILP<bool>>::reduce_to(&problem).unwrap();
    let target = reduction.target_problem();
    assert_eq!(target.num_vars(), 4);
    assert_eq!(target.num_constraints(), 2);

    let target_solution = ILPSolver::new().solve(target).unwrap();
    let solution = reduction.extract_solution(&target_solution).unwrap();
    assert_eq!(solution, vec![true, false, true, true]);
    println!("{}", problem.evaluate(&solution).unwrap()); // Max(3)
}

The target has one binary variable per set and a constraint for each element shared by multiple sets. extract_solution maps a target solution back to the source solution type. ILPSolver::new().solve(&problem) executes the exact variant’s registered ILP pipeline and returns its source solution.

Discover and run a path

Search uses exact variants. This discovers a route from Factoring to SpinGlass and executes it:

use problemreductions::models::algebraic::ILP;
use problemreductions::prelude::*;
use problemreductions::rules::{ReductionGraph, ReductionMode};
use problemreductions::solvers::ILPSolver;
use problemreductions::topology::SimpleGraph;
    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 paths = graph.find_all_paths_mode(
        "Factoring",
        &src_var,
        "SpinGlass",
        &dst_var,
        ReductionMode::Witness,
    );
    let rpath = paths
        .iter()
        .find(|path| path.type_names() == ["Factoring", "CircuitSAT", "SpinGlass"])
        .expect("explicit Factoring -> CircuitSAT -> SpinGlass route");
    println!("  {}", rpath);
    let factoring = Factoring::with_factor_bits(
        6, // target_product:  find p × q = 6
        2, // num_bits_first:  p is a 2-bit factor
        2, // num_bits_second: q is a 2-bit factor
    );

let reduction = graph.reduce_along_path(rpath, &factoring).unwrap().unwrap();
let target: &SpinGlass<SimpleGraph, f64> = reduction.target_problem();
// Solve `target`, then call reduction.extract_solution(&target_solution).

extract_solution walks the intermediate mappings in reverse. The full example also solves factoring through a direct ILP reduction and checks that the recovered factors multiply to 6:

cargo run --example chained_reduction_factoring_to_spinglass

Solver contracts

Every successful solve returns the problem's Solution. Evaluate it against the source with Problem::evaluate, which returns Result<P::Value, EvaluationError>. Path discovery enumerates routes; it does not rank them or register a solver capability. See the solver API.

API reference

Browse the Rust API →

The API is generated from Rust source with rustdoc. Start with models, reduction contracts, or solvers.

Run make doc to build the guides and API locally. For short runnable examples, see getting started.

Design

This guide covers the library internals for contributors.

See Numeric types and arithmetic before choosing numeric fields or implementing arithmetic in a model or reduction.

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 Solution;                         // e.g., Vec<bool>, permutation, tuple
    type Value: Clone;                     // e.g., Max<i64>, Or, Sum<i64>
    fn parameter_names() -> &'static [&'static str];
    fn parameters(&self) -> ProblemParameters;
    fn evaluate(&self, solution: &Self::Solution) -> Result<Self::Value, EvaluationError>;
    fn variant() -> Vec<(&'static str, &'static str)>; // e.g., [("graph", "SimpleGraph"), ("weight", "i64")]
    fn problem_type() -> ProblemType;      // default: registry lookup by NAME
}

• Problem — the base trait. Every problem declares a mathematical Solution type, evaluates that type directly, and reports its canonical instance parameters. For example, a 4-vertex MIS uses Vec<bool>; evaluate(&[true, false, true, false]) returns Ok(Max(Some(2))) if vertices 0 and 2 form an independent set, or Ok(Max(None)) if they share an edge. Inherent getters such as num_vertices() and num_edges() supply the named parameters used by reduction expressions.
• BruteForceProblem — the reference-solver capability for registered variants with a finite Cartesian coordinate space. Its dimensions() method and the Cartesian iterator belong to the brute-force solver, not to the mathematical Problem contract.
• Objective problems — typically use Max<V>, Min<V>, or Extremum<V> as Value.
• Feasibility problems — typically use Or.
• Solve contract — a successful solve always returns the problem's Solution; a global count or statistic without a representative solution is not a Problem solve.
• Common aggregate wrappers — Max<V>, Min<V>, Sum<W>, Or, And, Extremum<V>, ExtremumSense.

Construction inputs

VariantEntry::inputs() describes the values a concrete constructor accepts. Models with a separate construction specification supply CreateSpec::inputs(); direct constructors use their declared fields. CLI creation, MCP creation, and pred show use this contract. Model-level catalog fields describe the model family; they are not a concrete variant's input schema. show exposes concrete inputs in JSON and labels them Inputs in text.

Unit-valued data are implicit in One variants. For example, MVC/One accepts a graph, while MVC/i64 also accepts vertex weights. Constructors derive unit-vector lengths from the graph, set family, or task deadlines. Internal Vec<One> storage and persisted instance JSON remain independent of construction inputs. Supplying an undeclared weight or length input is an error, even when every value is one.

Decision<P> composes the registered inputs of P with an objective bound and calls P's registered constructor before wrapping the result. It does not repeat the inner input schema or deserialize construction inputs as persisted model JSON.

Numeric types and arithmetic

Numeric formats are selected by semantic role:

• usize represents in-memory indices, collection lengths, and brute-force dimensions;
• u64 represents public problem parameters and the input/output values of reduction parameter expressions;
• i64 represents signed mathematical integers;
• bool represents Boolean variables; and
• finite f64 represents real or rational values when an approximate representation is part of the model contract.

usize is not a portable serialized parameter format, and u64 is not an index or general-purpose replacement for a model's mathematical integer domain.

Another numeric format requires sufficient justification from the mathematical problem or target schema. Required exceptions include BigUint in Factoring, SubsetSum, SubsetProduct, QuadraticCongruences, and QuadraticDiophantineEquations, where arbitrary precision is part of the problem, and One in unweighted variants, where the type represents the unit-weight domain. Implementation convenience is not sufficient justification. There is no i32 model or I/O numeric format.

This contract applies only at model, result, reduction-target, and external I/O boundaries; implementation-local values are outside its scope. For example, SpinGlass couplings and its objective result use i64, while the temporary {−1, +1} spin values used inside evaluate() need not. A reduction's temporary calculations are also outside the contract, but numeric fields written into its target model must follow the target model's numeric format.

Weight variants are One, i64, and f64, with One ⊂ i64 ⊂ f64. i64 → f64 is a fallible reduction using a checked conversion in ±(2^53-1), not as f64.

Arithmetic

• Keep arithmetic in the declared type. Exact values use checked i64 operations; approximate values use finite f64 operations.
• Constructors and reductions reject an arithmetic step that would overflow i64 when producing a stored field. They do not cap every magnitude at 2^53-1. evaluate() never widens, wraps, saturates, or silently approximates.
• Do not promote an i64 calculation to i128, BigInt, or BigUint to accept a larger instance.

Boundaries

• Use From only for value-preserving conversions and TryFrom when range, sign, or domain can change. Do not use as for model-derived values.
• Converting a registered parameter getter from usize to u64 is an internal invariant of Problem::parameters(), not a recoverable construction error. A valid instance's registered parameters must already fit u64; the implementation checks this conversion to prevent silent truncation.
• Symbolic parameter evaluation may use arbitrary-precision integers for local intermediate arithmetic, but a materialized ProblemParameters must fit u64.
• An i64 to f64 conversion is explicit and fallible: it succeeds only for |value| ≤ 2^53-1. Use one shared helper at weight casts, solver adapters, and other exact-to-float hubs.
• A lattice-to-UnitDiskGraph reduction converts coordinates fallibly and rejects a stored f64 geometry that would change source adjacency.
• Rust constructors keep i64 fields as i64. CLI and MCP JSON encoding of an i64 with |value| > 2^53-1 errors; there is no string encoding and no clamping.

Variant System

A single problem name like MaximumIndependentSet can have multiple variants. Each variant is identified by dimension-value pairs such as {graph: "SimpleGraph", weight: "i64"}. Concrete variants are registered nodes in the reduction graph, and explicit reduction rules connect them.

Variant types fall into three categories:

• Graph type — SimpleGraph, PlanarGraph, BipartiteGraph, UnitDiskGraph, KingsSubgraph, TriangularSubgraph.
• Weight type — One (unweighted), i64, 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", "i64"
}

impl_variant_param!(SimpleGraph, "graph");

impl_variant_param!(KN, "k", k: None);

impl_variant_param!(K3, "k", k: Some(3));

impl_variant_reduction!(
    MaximumIndependentSet,
    <UnitDiskGraph, i64> => <SimpleGraph, i64>,
    fields: [num_vertices, num_edges],
    |src| MaximumIndependentSet::new(
        SimpleGraph::new(
            src.num_vertices(),
            Graph::edges(src.graph()),
        ),
        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: &Vec<bool>,
    ) -> crate::rules::ExtractionResult<Vec<bool>> {
        crate::rules::traits::validate_target_solution(self.target_problem(), target_sol)?;
        Ok(target_sol.iter().map(|&x| !x).collect())
    }
}

Solution extraction contract

ReductionResult::extract_solution accepts one complete target configuration and returns the source configuration defined by the reduction. Extraction is a fallible boundary, not a recovery mechanism:

1. In every direct extractor, call validate_target_solution() once before indexing or decoding. Composed extractors delegate this check.
2. Validate any structure required by the inverse mapping, such as exactly-one blocks, permutations, paths, flows, or schedules.
3. Apply the reduction's mathematical inverse once and return a source configuration with the required length and domains.
4. Return ExtractionError when a precondition is not satisfied.

Do not truncate or pad input, substitute zero for missing data, select the first of several invalid candidates, retry with another mapping, or panic on caller-provided configuration data. Empty and singleton instances should flow through the same mathematical mapping unless the reduction itself has a genuine mathematical case distinction.

Zero and sentinel values remain valid when the source model explicitly gives them meaning. For example, MaximumCommonEdgeSubgraph includes an "unmapped" sentinel in its source dimensions. Missing target data must never be interpreted as that sentinel.

Each conditional in an extractor should therefore either reject a named invariant violation or implement a case in the reduction's mathematics. A normal extractor has one validation phase followed by one decoding phase; it does not accumulate compatibility or fallback branches.

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

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

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: "i64"}).
• Edges come from explicit #[reduction] registrations, including cross-problem and same-problem variant reductions.

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>.

A rule has one relation for all of its formulas: either an exact equality or an upper bound. Composition keeps exact formulas exact only when every step is exact; every other combination is an upper bound. Concrete-instance measurement remains a separate execution API.

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

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

Executable paths

Execute an explicitly selected path with ReductionGraph::reduce_along_path:

let reduction = graph.reduce_along_path(rpath, &factoring_instance)?.unwrap();
let target: &SpinGlass<SimpleGraph, f64> = reduction.target_problem();
let source_solution = reduction.extract_solution(&target_solution)?;

The returned ReductionChain stores each intermediate reduction and extracts the source solution by applying the inverse mappings in reverse order. Construction returns ReductionError; extraction returns ExtractionError.

#[reduction(
transform = upper_bound {
    num_vars = "num_vertices + num_edges",
    num_clauses = "3 * num_edges",
},
unavailable = {
    encoding_bits = "coefficient magnitudes are not tracked",
},
})]
impl ReduceTo<Target> for Source { ... }

Input:  ProblemParameters { num_vertices: 10, num_edges: 15 }
Output: ProblemParameters { num_vars: 25 }

Solvers

The reference solver exposes a direct typed operation:

BruteForce::solve(&problem) -> Result<Option<P::Solution>, SolveError>

Some(solution) is a successful exact solve, None means exhaustive search proved infeasibility, and Err reports an operational failure.

ILP results are optimal or infeasible according to HiGHS numerical tolerances; zero MIP gaps do not imply mathematical exactness. Integer extraction rounds variable assignments, validates the original constraints, and recomputes the source objective with checked integer arithmetic. Floating-point objective comparisons in numerical regression tests use an explicit acceptance policy in source units (absolute and relative tolerances of 1e-7 for the QUBO solver regression), separate from the 1e-6 variable-rounding tolerance. This test policy is not a universal bound on backend objective error.

When an ILP target witness misses a source decision threshold, the solver returns ILPSolveError::UnresolvedDecision, not infeasibility: the witness alone cannot prove that no qualifying source solution exists.

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, i64> = from_json(&json)?;

Contributing

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

Open problems

To be released.