Problem Reductions

A Rust library for reducing NP-hard problems.

Overview

problemreductions provides implementations of various NP-hard computational problems and reduction rules between them. It is designed for algorithm research, education, and quantum optimization studies.

Features

• 18+ Problem Types: Implementations of classic NP-hard problems
• Type-Safe Reductions: Compile-time verified problem transformations
• BruteForce Solver: For testing and verification on small instances
• Topology Types: HyperGraph and UnitDiskGraph support
• File I/O: JSON serialization for all problem types
• Truth Tables: Utilities for logic gadget construction

Quick Example

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

// Create an Independent Set problem on a triangle graph
let problem = IndependentSet::<i32>::new(3, vec![(0, 1), (1, 2), (0, 2)]);

// Solve with brute force
let solver = BruteForce::new();
let solutions = solver.find_best(&problem);

// Maximum independent set in a triangle has size 1
assert!(solutions.iter().all(|s| s.iter().sum::<usize>() == 1));
}

Problem Categories

License

MIT License

Getting Started

Installation

Add to your Cargo.toml:

[dependencies]
problemreductions = "0.1"

Basic Usage

Creating a Problem

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

// Independent Set on a path graph
let is = IndependentSet::<i32>::new(4, vec![(0, 1), (1, 2), (2, 3)]);

// Vertex Cover on the same graph
let vc = VertexCovering::<i32>::new(4, vec![(0, 1), (1, 2), (2, 3)]);

// QUBO problem
let qubo = QUBO::from_matrix(vec![
    vec![1.0, -2.0],
    vec![0.0, 1.0],
]);
}

Solving a Problem

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem = IndependentSet::<i32>::new(4, vec![(0, 1), (1, 2), (2, 3)]);
let solver = BruteForce::new();
let solutions = solver.find_best(&problem);

println!("Found {} optimal solutions", solutions.len());
for sol in &solutions {
    println!("  Solution: {:?}", sol);
}
}

Applying Reductions

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

// Create an Independent Set problem
let is = IndependentSet::<i32>::new(4, vec![(0, 1), (1, 2)]);

// Reduce to Vertex Cover
let result = ReduceTo::<VertexCovering<i32>>::reduce_to(&is);
let vc = result.target_problem();

// Solve the reduced problem
let solver = BruteForce::new();
let vc_solutions = solver.find_best(vc);

// Extract solution back to original problem
let is_solution = result.extract_solution(&vc_solutions[0]);
}

Next Steps

• Learn about Problem Types
• Explore Available Reductions
• Check out the API Reference

Problem Types

This library implements 18+ NP-hard computational problems across several categories.

Categories

Graph Problems

Problems defined on graphs with vertices and edges:

• IndependentSet: Find maximum weight set of non-adjacent vertices
• VertexCovering: Find minimum weight set covering all edges
• MaxCut: Partition vertices to maximize cut weight
• Coloring: Assign colors minimizing conflicts
• DominatingSet: Find minimum set dominating all vertices
• MaximalIS: Find maximal independent sets
• Matching: Find maximum weight matching

Learn more about Graph Problems

Satisfiability Problems

Boolean satisfaction problems:

• Satisfiability (SAT): Find satisfying assignments for CNF formulas
• CircuitSAT: Satisfy boolean circuits
• Factoring: Factor integers (reducible to SAT)

Learn more about Satisfiability Problems

Optimization Problems

Continuous optimization on discrete domains:

• SpinGlass: Ising model Hamiltonian minimization
• QUBO: Quadratic unconstrained binary optimization

Learn more about Optimization Problems

Set Problems

Problems involving set collections:

• SetCovering: Minimum weight cover of universe
• SetPacking: Maximum weight packing of disjoint sets

Learn more about Set Problems

Specialized Problems

Domain-specific problems:

• PaintShop: Minimize color switches
• BicliqueCover: Cover bipartite graph with bicliques
• BMF: Boolean matrix factorization

Learn more about Specialized Problems

Common Interface

All problems implement the Problem trait:

#![allow(unused)]
fn main() {
pub trait Problem {
    type Size;

    fn num_variables(&self) -> usize;
    fn num_flavors(&self) -> usize;
    fn problem_size(&self) -> ProblemSize;
    fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size>;
    fn energy_mode(&self) -> EnergyMode;
}
}

Graph Problems

Graph problems are optimization problems defined on graph structures. This library provides a template-based approach where all graph problems share common infrastructure while having problem-specific constraints.

Design Overview

All graph problems use the GraphProblem<C, G, W> template:

• C: GraphConstraint - Defines the problem-specific constraint (e.g., independent set, vertex cover)
• G: Graph - The graph topology (defaults to SimpleGraph)
• W - Weight type (defaults to i32)

Type aliases provide convenient access:

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;
use problemreductions::topology::{SimpleGraph, UnitDiskGraph};

// These are equivalent - defaults to SimpleGraph and i32 weights
let problem: IndependentSetT = IndependentSetT::new(4, vec![(0, 1), (1, 2)]);
let problem: IndependentSetT<SimpleGraph, i32> = IndependentSetT::new(4, vec![(0, 1), (1, 2)]);

// With custom weight type
let weighted: IndependentSetT<SimpleGraph, f64> = IndependentSetT::with_weights(
    4,
    vec![(0, 1), (1, 2)],
    vec![1.0, 2.0, 3.0, 4.0]
);

// On different graph topology (e.g., for quantum hardware)
let udg = UnitDiskGraph::new(vec![(0.0, 0.0), (1.0, 0.0), (2.0, 0.0)], 1.5);
let quantum_problem: IndependentSetT<UnitDiskGraph> = IndependentSetT::from_graph(udg);
}

See Graph Topology for details on graph types.

IndependentSetT

Find a maximum weight set of vertices where no two are adjacent.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem: IndependentSetT = IndependentSetT::new(4, vec![(0, 1), (1, 2), (2, 3)]);
let solver = BruteForce::new();
let solutions = solver.find_best(&problem);
// Maximum IS on a path of 4 vertices has size 2 (vertices 0,2 or 1,3)
}

Constraint: For each edge (u, v), at most one of u or v can be selected.

Objective: Maximize sum of weights of selected vertices.

VertexCoverT

Find a minimum weight set of vertices that covers all edges.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem: VertexCoverT = VertexCoverT::new(4, vec![(0, 1), (1, 2), (2, 3)]);
let solver = BruteForce::new();
let solutions = solver.find_best(&problem);
// Minimum vertex cover on a path of 4 vertices has size 2
}

Constraint: For each edge (u, v), at least one of u or v must be selected.

Objective: Minimize sum of weights of selected vertices.

Relationship with Independent Set: IS and VC are complements. For any graph with n vertices:

|max IS| + |min VC| = n

A set S is an independent set if and only if V \ S is a vertex cover.

CliqueT

Find a maximum weight complete subgraph.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem: CliqueT = CliqueT::new(4, vec![(0, 1), (0, 2), (1, 2), (2, 3)]);
// Vertices 0, 1, 2 form a triangle (clique of size 3)
}

Constraint: Every pair of selected vertices must be connected by an edge.

Objective: Maximize sum of weights of selected vertices.

Relationship with Independent Set: Finding a maximum clique in G is equivalent to finding a maximum independent set in the complement graph G'.

MaxCut

Partition vertices into two sets to maximize the weight of edges between them.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem = MaxCut::new(3, vec![(0, 1, 2), (1, 2, 3), (0, 2, 1)]);
// Edge weights: (0,1)=2, (1,2)=3, (0,2)=1
}

Note: MaxCut uses a different structure as it requires edge weights directly.

Coloring

Assign k colors to vertices minimizing adjacent same-color pairs.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem = Coloring::new(4, 3, vec![(0, 1), (1, 2), (2, 3)]);
// 4 vertices, 3 colors available
}

Available Graph Problems

Using with Different Topologies

The template design enables topology-aware reductions. For example, reducing SAT to Independent Set can target different graph types:

#![allow(unused)]
fn main() {
use problemreductions::topology::{SimpleGraph, UnitDiskGraph};
use problemreductions::models::graph::IndependentSetT;

// Standard reduction produces arbitrary graph
// impl ReduceTo<IndependentSetT<SimpleGraph>> for Satisfiability { ... }

// Topology-aware reduction produces unit disk graph
// impl ReduceTo<IndependentSetT<UnitDiskGraph>> for Satisfiability { ... }
}

This is particularly useful for quantum computing where neutral atom arrays naturally implement unit disk graph connectivity.

Common Operations

All graph problems implement the OptProblem trait:

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem: IndependentSetT = IndependentSetT::new(4, vec![(0, 1), (1, 2), (2, 3)]);

// Check solution validity and size
let solution = vec![1, 0, 1, 0];  // Select vertices 0 and 2
let result = problem.solution_size(&solution);
assert!(result.is_valid);
assert_eq!(result.size, 2);

// Get problem parameters
assert_eq!(problem.num_variables(), 4);
assert_eq!(problem.num_flavors(), 2);  // Binary: selected (1) or not (0)

// Check optimization direction
assert!(problem.energy_mode().is_maximization());
}

CSP Interface

Graph problems also implement the ConstraintSatisfactionProblem trait:

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem: IndependentSetT = IndependentSetT::new(3, vec![(0, 1), (1, 2)]);

// Get constraints (one per edge)
let constraints = problem.constraints();
assert_eq!(constraints.len(), 2);

// Get objectives (one per vertex)
let objectives = problem.objectives();
assert_eq!(objectives.len(), 3);

// Check if solution satisfies all constraints
let solution = vec![1, 0, 1];
assert!(problem.is_satisfied(&solution));
}

Satisfiability Problems

Satisfiability problems involve finding assignments to boolean variables that satisfy given constraints.

SAT (Boolean Satisfiability)

The Boolean Satisfiability Problem (SAT) asks whether there exists an assignment of truth values to variables that makes a given boolean formula evaluate to TRUE.

Definition: Given a CNF (Conjunctive Normal Form) formula with n variables and m clauses, find an assignment that satisfies all clauses.

A CNF formula is a conjunction (AND) of clauses, where each clause is a disjunction (OR) of literals. A literal is either a variable (x) or its negation (NOT x).

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

// Formula: (x1 OR x2) AND (NOT x1 OR x3)
let problem = Satisfiability::<i32>::new(
    3,  // 3 variables
    vec![
        CNFClause::new(vec![1, 2]),     // x1 OR x2
        CNFClause::new(vec![-1, 3]),    // NOT x1 OR x3
    ],
);

let solver = BruteForce::new();
let solutions = solver.find_best(&problem);
}

Complexity: SAT is NP-complete (Cook-Levin theorem, 1971).

KSatisfiability (k-SAT)

A restricted version where every clause has exactly k literals.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

// 3-SAT formula: each clause has exactly 3 literals
let problem = KSatisfiability::<3, i32>::new(
    4,  // 4 variables
    vec![
        KSATClause::new([1, 2, 3]),      // x1 OR x2 OR x3
        KSATClause::new([-1, -2, 4]),    // NOT x1 OR NOT x2 OR x4
    ],
);
}

Note: 3-SAT remains NP-complete, while 2-SAT is in P.

CircuitSAT

CircuitSAT extends SAT to boolean circuits. Instead of a CNF formula, the input is a circuit of logic gates (AND, OR, NOT, XOR).

Definition: Given a boolean circuit, find an assignment to input variables such that the circuit outputs TRUE.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

// Circuit computing: output = (x AND y) XOR z
let circuit = Circuit::new(vec![
    Assignment::new(
        vec!["temp".to_string()],
        BooleanExpr::and(vec![BooleanExpr::var("x"), BooleanExpr::var("y")]),
    ),
    Assignment::new(
        vec!["output".to_string()],
        BooleanExpr::xor(vec![BooleanExpr::var("temp"), BooleanExpr::var("z")]),
    ),
]);
let problem = CircuitSAT::<i32>::new(circuit);

let solver = BruteForce::new();
let solutions = solver.find_best(&problem);
}

Supported Gate Types

• BooleanExpr::and(inputs) - AND gate
• BooleanExpr::or(inputs) - OR gate
• BooleanExpr::not(input) - NOT gate
• BooleanExpr::xor(inputs) - XOR gate
• BooleanExpr::var(name) - Input variable
• BooleanExpr::constant(value) - Constant TRUE/FALSE

Complexity: CircuitSAT is NP-complete.

Reduction to SpinGlass

CircuitSAT can be reduced to SpinGlass (Ising model) using gate gadgets. Each logic gate is mapped to a set of spin interactions that encode the gate's truth table as energy penalties.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let circuit = Circuit::new(vec![
    Assignment::new(
        vec!["c".to_string()],
        BooleanExpr::and(vec![BooleanExpr::var("x"), BooleanExpr::var("y")]),
    ),
]);
let problem = CircuitSAT::<i32>::new(circuit);

// Reduce to SpinGlass
let reduction = ReduceTo::<SpinGlass<i32>>::reduce_to(&problem);
let sg = reduction.target_problem();
}

Factoring

Integer factorization expressed as a decision problem. Given a composite number N, find non-trivial factors p and q such that p * q = N.

Definition: Given N and bit sizes m and n, find m-bit integer p and n-bit integer q such that p * q = N.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

// Factor 15 using 4-bit factors
// Arguments: (m bits for p, n bits for q, target N)
let problem = Factoring::new(4, 4, 15);

// Read a candidate solution
let solution = vec![1, 1, 0, 0, 1, 0, 1, 0]; // p=3, q=5 in little-endian
let (p, q) = problem.read_factors(&solution);
assert_eq!(p * q, 15);
}

How it Works

The Factoring problem stores:

• m: Number of bits for the first factor
• n: Number of bits for the second factor
• target: The number to factor (N)

Solutions are bit vectors where:

• First m bits encode p (little-endian)
• Next n bits encode q (little-endian)

Reduction to CircuitSAT

Factoring reduces to CircuitSAT by constructing a multiplier circuit:

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let factoring = Factoring::new(4, 4, 15);

// Reduce to CircuitSAT (multiplier circuit)
let reduction = ReduceTo::<CircuitSAT<i32>>::reduce_to(&factoring);
let circuit_sat = reduction.target_problem();

// The circuit computes p * q and constrains output = 15
// Solving gives the factors
}

The reduction builds an array multiplier circuit with:

• Input variables for p (m bits) and q (n bits)
• Multiplier cells computing partial products
• Output constraints fixing the product to equal N

Complexity: Factoring is believed to be hard classically but in BQP (solvable by quantum computers via Shor's algorithm).

Problem Relationships

Factoring --> CircuitSAT --> SpinGlass
                  |
                  v
            Satisfiability --> IndependentSet
                  |                  |
                  v                  v
              Coloring          SetPacking
                  |
                  v
           DominatingSet

All these problems are NP-complete (except Factoring, whose complexity is unknown but believed to be intermediate).

Optimization Problems

SpinGlass (Ising Model)

Minimize the Ising Hamiltonian: H = Σ J_ij s_i s_j + Σ h_i s_i

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem = SpinGlass::new(
    3,
    vec![((0, 1), -1.0), ((1, 2), 1.0)],  // Interactions
    vec![0.5, -0.5, 0.0],                  // On-site fields
);

let solver = BruteForce::new();
let solutions = solver.find_best(&problem);
}

QUBO

Quadratic Unconstrained Binary Optimization: minimize x^T Q x

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

// From matrix
let problem = QUBO::from_matrix(vec![
    vec![1.0, -2.0],
    vec![0.0, 1.0],
]);

// From linear and quadratic terms
let problem = QUBO::new(
    vec![1.0, -1.0],           // Linear (diagonal)
    vec![((0, 1), 0.5)],       // Quadratic (off-diagonal)
);
}

Relationship

SpinGlass and QUBO are equivalent via the transformation s = 2x - 1:

• x = 0 corresponds to s = -1
• x = 1 corresponds to s = +1

The library provides bidirectional reductions between them.

Set Problems

SetCovering

Find minimum weight collection of sets that covers all elements.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem = SetCovering::<i32>::new(
    5,  // Universe size
    vec![
        vec![0, 1, 2],
        vec![2, 3, 4],
        vec![0, 4],
    ],
);
}

SetPacking

Find maximum weight collection of pairwise disjoint sets.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem = SetPacking::<i32>::new(vec![
    vec![0, 1],
    vec![1, 2],  // Overlaps with first
    vec![2, 3],
    vec![4],
]);
}

Relationship to Graph Problems

SetPacking is equivalent to IndependentSet on the intersection graph:

• Each set becomes a vertex
• Overlapping sets are connected by edges

The library provides reductions between them.

Specialized Problems

PaintShop

Minimize color switches in a painting sequence where each car type needs both colors.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem = PaintShop::new(vec!["a", "b", "a", "b", "c", "c"]);
}

BicliqueCover

Cover edges of a bipartite graph using k bicliques.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem = BicliqueCover::new(
    2,  // Left vertices
    2,  // Right vertices
    vec![(0, 2), (0, 3), (1, 2), (1, 3)],  // Edges
    1,  // Number of bicliques
);
}

BMF (Boolean Matrix Factorization)

Factor a boolean matrix M into A * B with minimum rank.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem = BMF::new(
    vec![
        vec![true, true],
        vec![true, false],
    ],
    1,  // Rank
);
}

Reductions

Problem reductions allow transforming one NP-hard problem into another while preserving solution structure.

Why Reductions?

• Solve problems indirectly: Transform to a problem with a better solver
• Prove equivalence: Show problems have the same computational complexity
• Hardware mapping: Transform to problems supported by quantum hardware

Available Reductions

Reduction Traits

#![allow(unused)]
fn main() {
pub trait ReduceTo<T: Problem>: Problem {
    type Result: ReductionResult<Source = Self, Target = T>;
    fn reduce_to(&self) -> Self::Result;
}

pub trait ReductionResult: Clone {
    type Source: Problem;
    type Target: Problem;

    fn target_problem(&self) -> &Self::Target;
    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize>;
}
}

See:

• Using Reductions
• Available Reductions
• Reduction Graph

Using Reductions

Basic Usage

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

// Create source problem
let is = IndependentSet::<i32>::new(4, vec![(0, 1), (1, 2), (2, 3)]);

// Reduce to target problem
let result = ReduceTo::<VertexCovering<i32>>::reduce_to(&is);
let vc = result.target_problem();

// Solve target problem
let solver = BruteForce::new();
let vc_solutions = solver.find_best(vc);

// Extract solution back to source problem
let is_solution = result.extract_solution(&vc_solutions[0]);

// Verify solution is valid
assert!(is.solution_size(&is_solution).is_valid);
}

Chaining Reductions

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let sp = SetPacking::<i32>::new(vec![
    vec![0, 1],
    vec![1, 2],
    vec![2, 3],
]);

// SetPacking -> IndependentSet -> VertexCovering
let sp_to_is = ReduceTo::<IndependentSet<i32>>::reduce_to(&sp);
let is = sp_to_is.target_problem();

let is_to_vc = ReduceTo::<VertexCovering<i32>>::reduce_to(is);
let vc = is_to_vc.target_problem();

// Solve and extract back through the chain
let solver = BruteForce::new();
let vc_solutions = solver.find_best(vc);
let is_solution = is_to_vc.extract_solution(&vc_solutions[0]);
let sp_solution = sp_to_is.extract_solution(&is_solution);
}

Type Safety

The reduction system is compile-time verified. Invalid reductions won't compile:

#![allow(unused)]
fn main() {
// This won't compile - no reduction from QUBO to SetPacking
let result = ReduceTo::<SetPacking<i32>>::reduce_to(&qubo);
}

Available Reductions

This page documents all reduction rules implemented in the library, with academic citations.

Graph Problem Reductions

IndependentSet <-> VertexCovering

These are complement problems on the same graph. A set S is an independent set if and only if V \ S is a vertex cover.

Citation: Karp, R. M. (1972). "Reducibility among Combinatorial Problems". In Miller, R. E.; Thatcher, J. W. (eds.). Complexity of Computer Computations. Plenum Press. pp. 85-103.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let is = IndependentSet::<i32>::new(4, vec![(0, 1), (1, 2)]);
let result = ReduceTo::<VertexCovering<i32>>::reduce_to(&is);
}

For any graph: |max IS| + |min VC| = n

IndependentSet <-> SetPacking

Based on the intersection graph equivalence. Each vertex becomes a set containing its incident edges.

Citation: Gavril, F. (1972). "Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph". SIAM Journal on Computing. 1 (2): 180-187.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let is = IndependentSet::<i32>::new(3, vec![(0, 1), (1, 2)]);
let result = ReduceTo::<SetPacking<i32>>::reduce_to(&is);
}

VertexCovering -> SetCovering

Each vertex becomes a set containing the edges it covers. The universe is the set of all edges.

Citation: Karp, R. M. (1972). "Reducibility among Combinatorial Problems". In Miller, R. E.; Thatcher, J. W. (eds.). Complexity of Computer Computations. Plenum Press. pp. 85-103.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let vc = VertexCovering::<i32>::new(3, vec![(0, 1), (1, 2)]);
let result = ReduceTo::<SetCovering<i32>>::reduce_to(&vc);
}

Matching -> SetPacking

Each edge (u, v) becomes a set {u, v}. A matching (no two edges share a vertex) corresponds to a set packing (no two sets overlap).

Citation: Edmonds, J. (1965). "Paths, Trees, and Flowers". Canadian Journal of Mathematics. 17: 449-467.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let matching = Matching::<i32>::new(4, vec![(0, 1), (1, 2), (2, 3)]);
let result = ReduceTo::<SetPacking<i32>>::reduce_to(&matching);
}

Optimization Reductions

SpinGlass <-> QUBO

Uses variable substitution s = 2x - 1 to convert between spin variables (±1) and binary variables (0/1).

Citation: Lucas, A. (2014). "Ising formulations of many NP problems". Frontiers in Physics. 2: 5.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let sg = SpinGlass::new(2, vec![((0, 1), -1.0)], vec![0.0, 0.0]);
let result = ReduceTo::<QUBO>::reduce_to(&sg);
}

SpinGlass <-> MaxCut

Direct mapping for pure interaction terms. On-site fields require an ancilla vertex connected to all spins.

Citation: Barahona, F. (1982). "On the computational complexity of Ising spin glass models". Journal of Physics A: Mathematical and General. 15 (10): 3241-3253.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let sg = SpinGlass::new(3, vec![((0, 1), 1), ((1, 2), 1)], vec![0, 0, 0]);
let result = ReduceTo::<MaxCut<i32>>::reduce_to(&sg);
}

SAT-Based Reductions

Satisfiability <-> KSatisfiability

Converts between general CNF-SAT and k-SAT (clauses with exactly k literals). Large clauses are split using auxiliary variables; small clauses are padded.

Citation: Cook, S. A. (1971). "The Complexity of Theorem-Proving Procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151-158.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let sat = Satisfiability::<i32>::new(3, vec![
    CNFClause::new(vec![1, 2, 3]),
    CNFClause::new(vec![-1, 2]),
]);
let result = ReduceTo::<KSatisfiability<3, i32>>::reduce_to(&sat);
}

Satisfiability -> IndependentSet

Each literal occurrence in a clause becomes a vertex. Edges connect conflicting literals (x and NOT x) and literals within the same clause.

Citation: Karp, R. M. (1972). "Reducibility among Combinatorial Problems". In Miller, R. E.; Thatcher, J. W. (eds.). Complexity of Computer Computations. Plenum Press. pp. 85-103.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let sat = Satisfiability::<i32>::new(2, vec![
    CNFClause::new(vec![1, 2]),
    CNFClause::new(vec![-1, -2]),
]);
let result = ReduceTo::<IndependentSet<i32>>::reduce_to(&sat);
}

Satisfiability -> Coloring

Uses gadget-based construction with three special colors (TRUE, FALSE, AUX). Variables are represented as vertex pairs, and OR-gadgets enforce clause satisfaction.

Citation: Garey, M. R.; Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let sat = Satisfiability::<i32>::new(2, vec![
    CNFClause::new(vec![1, 2]),
]);
let result = ReduceTo::<Coloring>::reduce_to(&sat);
}

Satisfiability -> DominatingSet

Variables and clauses become vertices. A variable vertex dominates clause vertices containing that literal.

Citation: Garey, M. R.; Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let sat = Satisfiability::<i32>::new(2, vec![
    CNFClause::new(vec![1, -2]),
]);
let result = ReduceTo::<DominatingSet<i32>>::reduce_to(&sat);
}

Circuit Reductions

CircuitSAT -> SpinGlass

Each logic gate is mapped to a spin glass gadget that encodes the gate's truth table as energy penalties.

Citation: Whitfield, J. D.; Faccin, M.; Biamonte, J. D. (2012). "Ground-state spin logic". EPL (Europhysics Letters). 99 (5): 57004.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let circuit = Circuit::new(vec![
    Assignment::new(vec!["c".to_string()],
        BooleanExpr::and(vec![BooleanExpr::var("x"), BooleanExpr::var("y")])),
]);
let problem = CircuitSAT::<i32>::new(circuit);
let result = ReduceTo::<SpinGlass<i32>>::reduce_to(&problem);
}

Factoring -> CircuitSAT

Constructs a multiplier circuit that computes p * q and constrains the output to equal the target number N. A satisfying assignment reveals the factors.

Citation: Folklore result using standard array multiplier circuits. The construction is well-known in hardware verification and circuit complexity.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

// Factor 15 with 4-bit factors
let factoring = Factoring::new(4, 4, 15);
let result = ReduceTo::<CircuitSAT<i32>>::reduce_to(&factoring);
}

Reduction Summary Table

Reduction Graph

The ReductionGraph allows discovering reduction paths between problem types.

Reduction Diagram

flowchart TD
    subgraph Specialized["Specialized Problems"]
        Factoring
    end

    subgraph Circuit["Circuit Problems"]
        CircuitSAT
    end

    subgraph SAT["Satisfiability Problems"]
        Satisfiability
        KSat["KSatisfiability<3>"]
    end

    subgraph Graph["Graph Problems"]
        IS["IndependentSet"]
        VC["VertexCovering"]
        Coloring
        DS["DominatingSet"]
        Matching
    end

    subgraph Set["Set Problems"]
        SP["SetPacking"]
        SC["SetCovering"]
    end

    subgraph Optimization["Optimization Problems"]
        SG_i32["SpinGlass<i32>"]
        SG_f64["SpinGlass<f64>"]
        QUBO["QUBO<f64>"]
        MaxCut["MaxCut<i32>"]
    end

    %% Factoring chain
    Factoring --> CircuitSAT
    CircuitSAT --> SG_i32

    %% SAT reductions
    Satisfiability <--> KSat
    Satisfiability --> IS
    Satisfiability --> Coloring
    Satisfiability --> DS

    %% Graph problem reductions
    IS <--> VC
    IS <--> SP
    VC --> SC
    Matching --> SP

    %% Optimization reductions
    SG_f64 <--> QUBO
    SG_i32 <--> MaxCut

    %% Styling
    style Factoring fill:#f9f,stroke:#333
    style CircuitSAT fill:#f9f,stroke:#333
    style Satisfiability fill:#bbf,stroke:#333
    style KSat fill:#bbf,stroke:#333
    style IS fill:#bfb,stroke:#333
    style VC fill:#bfb,stroke:#333
    style Coloring fill:#bfb,stroke:#333
    style DS fill:#bfb,stroke:#333
    style Matching fill:#bfb,stroke:#333
    style SP fill:#fbb,stroke:#333
    style SC fill:#fbb,stroke:#333
    style SG_i32 fill:#ff9,stroke:#333
    style SG_f64 fill:#ff9,stroke:#333
    style QUBO fill:#ff9,stroke:#333
    style MaxCut fill:#ff9,stroke:#333

Legend

Bidirectional arrows (<-->) indicate reductions exist in both directions.

Usage

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;
use problemreductions::rules::ReductionGraph;

let graph = ReductionGraph::new();

// Check if direct reduction exists
let has_direct = graph.has_direct_reduction::<IndependentSet<i32>, VertexCovering<i32>>();

// Find all paths between types
let paths = graph.find_paths::<SetPacking<i32>, VertexCovering<i32>>();

// Find shortest path
let shortest = graph.find_shortest_path::<SetPacking<i32>, VertexCovering<i32>>();

// Get statistics
println!("Types: {}, Reductions: {}", graph.num_types(), graph.num_reductions());
}

Registered Reductions

API

#![allow(unused)]
fn main() {
impl ReductionGraph {
    /// Create a new reduction graph with all registered reductions.
    pub fn new() -> Self;

    /// Check if a direct reduction exists from S to T.
    pub fn has_direct_reduction<S: 'static, T: 'static>(&self) -> bool;

    /// Find all paths from source to target type.
    pub fn find_paths<S: 'static, T: 'static>(&self) -> Vec<ReductionPath>;

    /// Find the shortest path from source to target type.
    pub fn find_shortest_path<S: 'static, T: 'static>(&self) -> Option<ReductionPath>;

    /// Get all registered problem type names.
    pub fn problem_types(&self) -> Vec<&'static str>;

    /// Get the number of registered problem types.
    pub fn num_types(&self) -> usize;

    /// Get the number of registered reductions.
    pub fn num_reductions(&self) -> usize;
}
}

Solvers

The library provides multiple solvers for finding optimal solutions to computational problems.

BruteForce Solver

A complete solver that enumerates all configurations. Guaranteed to find all optimal solutions but only practical for small instances.

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let problem: IndependentSetT = IndependentSetT::new(4, vec![(0, 1), (1, 2), (2, 3)]);
let solver = BruteForce::new();
let solutions = solver.find_best(&problem);

// Get solutions with their sizes
let solutions_with_size = solver.find_best_with_size(&problem);
}

Configuration

#![allow(unused)]
fn main() {
use problemreductions::prelude::*;

let solver = BruteForce::new()
    .valid_only(true);   // Only return valid solutions (default: true)

// For floating-point problems
let solver = BruteForce::with_tolerance(1e-6, 1e-6);
}

Performance

The brute-force solver enumerates all num_flavors^num_variables configurations. Use only for small instances (typically < 20 variables).

ILP Solver (Optional)

An Integer Linear Programming solver using HiGHS. Enables exact solving for much larger instances than brute force.

Enabling the ILP Feature

Add the ilp feature to your Cargo.toml:

[dependencies]
problemreductions = { version = "0.1", features = ["ilp"] }

Usage

use problemreductions::prelude::*;
use problemreductions::solvers::ILPSolver;

let problem: IndependentSetT = IndependentSetT::new(100, edges);
let solver = ILPSolver::new();

if let Some(solution) = solver.solve(&problem) {
    println!("Found solution: {:?}", solution);
}

// With time limit
let solver = ILPSolver::with_time_limit(60.0);  // 60 seconds

Working with ILP

The ILP solver works with the ILP problem type directly. Problems that implement ReduceTo<ILP> can be solved using the solve_reduced method.

use problemreductions::models::optimization::{ILP, LinearConstraint, ObjectiveSense};
use problemreductions::solvers::ILPSolver;

// Create an ILP directly
let ilp = ILP::binary(
    2,
    vec![LinearConstraint::le(vec![(0, 1.0), (1, 1.0)], 1.0)],
    vec![(0, 1.0), (1, 2.0)],
    ObjectiveSense::Maximize,
);

let solver = ILPSolver::new();
if let Some(solution) = solver.solve(&ilp) {
    println!("Solution: {:?}", solution);
}

Solving Problems via Reduction

For problems that implement ReduceTo<ILP>, use solve_reduced:

use problemreductions::solvers::ILPSolver;

let problem = SomeProblem::new(...); // Problem that implements ReduceTo<ILP>
let solver = ILPSolver::new();

if let Some(solution) = solver.solve_reduced(&problem) {
    println!("Solution: {:?}", solution);
}

Solver Trait

All solvers implement the Solver trait:

pub trait Solver {
    /// Find the best solution(s) for a problem.
    fn find_best<P: Problem>(&self, problem: &P) -> Vec<Vec<usize>>;

    /// Find the best solution(s) with their sizes.
    fn find_best_with_size<P: Problem>(
        &self,
        problem: &P,
    ) -> Vec<(Vec<usize>, SolutionSize<P::Size>)>;
}

Comparing Solvers

use problemreductions::prelude::*;
use problemreductions::solvers::ILPSolver;

let problem: IndependentSetT = IndependentSetT::new(15, edges);

// Brute force (complete but slow)
let bf = BruteForce::new();
let bf_solutions = bf.find_best(&problem);

// ILP (fast but returns single solution)
let ilp = ILPSolver::new();
let ilp_solution = ilp.solve(&problem);

// Verify both find the same optimal value
let bf_size = problem.solution_size(&bf_solutions[0]).size;
let ilp_size = problem.solution_size(&ilp_solution.unwrap()).size;
assert_eq!(bf_size, ilp_size);

Graph Topology

This module provides the Graph trait and various graph implementations for defining computational problems on different graph structures.

Design Philosophy

Following Julia's Graphs.jl pattern, problems are generic over graph type. This enables topology-aware reductions:

#![allow(unused)]
fn main() {
use problemreductions::topology::{Graph, SimpleGraph, UnitDiskGraph};
use problemreductions::models::graph::IndependentSetT;

// Standard problem on SimpleGraph (default)
let is_simple: IndependentSetT = IndependentSetT::new(4, vec![(0, 1), (1, 2)]);

// Same problem on UnitDiskGraph (for quantum hardware)
let udg = UnitDiskGraph::new(positions, radius);
let is_udg: IndependentSetT<UnitDiskGraph> = IndependentSetT::from_graph(udg);
}

Different reductions can target different topologies:

#![allow(unused)]
fn main() {
// Standard reduction -> arbitrary graph
impl ReduceTo<IndependentSetT<SimpleGraph>> for Satisfiability { ... }

// Topology-aware reduction -> unit disk graph (using geometric gadgets)
impl ReduceTo<IndependentSetT<UnitDiskGraph>> for Satisfiability { ... }
}

The Graph Trait

All graph types implement the Graph trait:

#![allow(unused)]
fn main() {
pub trait Graph: Clone + Send + Sync {
    fn num_vertices(&self) -> usize;
    fn num_edges(&self) -> usize;
    fn edges(&self) -> Vec<(usize, usize)>;
    fn has_edge(&self, u: usize, v: usize) -> bool;
    fn neighbors(&self, v: usize) -> Vec<usize>;
    fn degree(&self, v: usize) -> usize;  // default impl
    fn is_empty(&self) -> bool;            // default impl
}
}

SimpleGraph

The default graph type for most problems. Wraps petgraph's UnGraph with convenient constructors:

#![allow(unused)]
fn main() {
use problemreductions::topology::SimpleGraph;

// Create from vertices and edges
let g = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);

// Factory methods
let complete = SimpleGraph::complete(4);    // K4
let path = SimpleGraph::path(5);            // 0-1-2-3-4
let cycle = SimpleGraph::cycle(4);          // 0-1-2-3-0
let star = SimpleGraph::star(5);            // 0 connected to 1,2,3,4
let grid = SimpleGraph::grid(3, 4);         // 3x4 grid graph
}

UnitDiskGraph

Geometric graphs where vertices have 2D positions and edges connect vertices within a distance threshold. Useful for:

• Quantum computing (neutral atom arrays)
• Wireless network problems
• Geometric constraint satisfaction

#![allow(unused)]
fn main() {
use problemreductions::topology::UnitDiskGraph;

let positions = vec![
    (0.0, 0.0),
    (1.0, 0.0),   // Distance 1.0 from (0,0)
    (2.5, 0.0),   // Distance 2.5 from (0,0)
];

let udg = UnitDiskGraph::new(positions, 1.5);
// Edges: 0-1 (distance 1.0 <= 1.5)
// No edge 0-2 (distance 2.5 > 1.5)
// No edge 1-2 (distance 1.5 <= 1.5, so actually connected!)

// Grid factory
let grid_udg = UnitDiskGraph::grid(3, 4, 1.0, 1.5);
}

Using with Problems

#![allow(unused)]
fn main() {
use problemreductions::topology::UnitDiskGraph;
use problemreductions::models::graph::IndependentSetT;

// Create UDG representing quantum hardware connectivity
let udg = UnitDiskGraph::new(atom_positions, interaction_radius);

// Define Independent Set problem on this topology
let problem: IndependentSetT<UnitDiskGraph> = IndependentSetT::from_graph(udg);

// Solve for maximum independent set
let solutions = solver.find_best(&problem);
}

HyperGraph

Generalized graphs where edges (hyperedges) can connect any number of vertices. Note: HyperGraph does NOT implement the Graph trait since hyperedges are fundamentally different from 2-vertex edges.

#![allow(unused)]
fn main() {
use problemreductions::topology::HyperGraph;

let hg = HyperGraph::new(5, vec![
    vec![0, 1, 2],  // Hyperedge connecting 3 vertices
    vec![2, 3, 4],  // Another hyperedge
]);

assert_eq!(hg.num_vertices(), 5);
assert_eq!(hg.num_edges(), 2);

// Get neighbors (vertices sharing a hyperedge)
let neighbors = hg.neighbors(2);  // [0, 1, 3, 4]

// Check if it's actually a regular graph
if hg.is_regular_graph() {
    let edges = hg.to_graph_edges().unwrap();
}
}

API Reference

Graph Trait

#![allow(unused)]
fn main() {
pub trait Graph: Clone + Send + Sync {
    fn num_vertices(&self) -> usize;
    fn num_edges(&self) -> usize;
    fn edges(&self) -> Vec<(usize, usize)>;
    fn has_edge(&self, u: usize, v: usize) -> bool;
    fn neighbors(&self, v: usize) -> Vec<usize>;
    fn degree(&self, v: usize) -> usize;
    fn is_empty(&self) -> bool;
    fn for_each_edge<F>(&self, f: F) where F: FnMut(usize, usize);
}
}

SimpleGraph

#![allow(unused)]
fn main() {
impl SimpleGraph {
    pub fn new(num_vertices: usize, edges: Vec<(usize, usize)>) -> Self;
    pub fn empty(num_vertices: usize) -> Self;
    pub fn complete(num_vertices: usize) -> Self;
    pub fn path(num_vertices: usize) -> Self;
    pub fn cycle(num_vertices: usize) -> Self;
    pub fn star(num_vertices: usize) -> Self;
    pub fn grid(rows: usize, cols: usize) -> Self;
}
}

UnitDiskGraph

#![allow(unused)]
fn main() {
impl UnitDiskGraph {
    pub fn new(positions: Vec<(f64, f64)>, radius: f64) -> Self;
    pub fn unit(positions: Vec<(f64, f64)>) -> Self;  // radius = 1.0
    pub fn grid(rows: usize, cols: usize, spacing: f64, radius: f64) -> Self;
    pub fn radius(&self) -> f64;
    pub fn position(&self, v: usize) -> Option<(f64, f64)>;
    pub fn positions(&self) -> &[(f64, f64)];
    pub fn vertex_distance(&self, u: usize, v: usize) -> Option<f64>;
    pub fn bounding_box(&self) -> Option<((f64, f64), (f64, f64))>;
}
}

HyperGraph

#![allow(unused)]
fn main() {
impl HyperGraph {
    pub fn new(num_vertices: usize, edges: Vec<Vec<usize>>) -> Self;
    pub fn empty(num_vertices: usize) -> Self;
    pub fn num_vertices(&self) -> usize;
    pub fn num_edges(&self) -> usize;
    pub fn edges(&self) -> &[Vec<usize>];
    pub fn edge(&self, index: usize) -> Option<&Vec<usize>>;
    pub fn has_edge(&self, edge: &[usize]) -> bool;
    pub fn neighbors(&self, v: usize) -> Vec<usize>;
    pub fn degree(&self, v: usize) -> usize;
    pub fn edges_containing(&self, v: usize) -> Vec<&Vec<usize>>;
    pub fn max_edge_size(&self) -> usize;
    pub fn is_regular_graph(&self) -> bool;
    pub fn to_graph_edges(&self) -> Option<Vec<(usize, usize)>>;
}
}

File I/O

All problem types support JSON serialization.

Writing Problems

#![allow(unused)]
fn main() {
use problemreductions::io::{write_problem, FileFormat};
use problemreductions::prelude::*;

let problem = IndependentSet::<i32>::new(4, vec![(0, 1), (1, 2)]);
write_problem(&problem, "problem.json", FileFormat::Json).unwrap();
}

Reading Problems

#![allow(unused)]
fn main() {
use problemreductions::io::{read_problem, FileFormat};
use problemreductions::prelude::*;

let problem: IndependentSet<i32> = read_problem("problem.json", FileFormat::Json).unwrap();
}

String Serialization

#![allow(unused)]
fn main() {
use problemreductions::io::{to_json, from_json};
use problemreductions::prelude::*;

let problem = IndependentSet::<i32>::new(3, vec![(0, 1)]);

// Serialize to string
let json = to_json(&problem).unwrap();

// Deserialize from string
let restored: IndependentSet<i32> = from_json(&json).unwrap();
}

File Formats

API Reference

Full API documentation is available at docs.rs/problemreductions or in the generated rustdoc.

Quick Links

Core Traits

• Problem - Base trait for all problems
• ConstraintSatisfactionProblem - CSP-specific trait
• ReduceTo - Reduction trait
• ReductionResult - Reduction result trait
• Solver - Solver trait

Problem Types

Graph

• IndependentSet
• VertexCovering
• MaxCut
• Coloring
• DominatingSet
• MaximalIS
• Matching

Optimization

• SpinGlass
• QUBO

Set

• SetCovering
• SetPacking

Satisfiability

• Satisfiability
• CircuitSAT
• Factoring

Utilities

• ReductionGraph
• TruthTable
• HyperGraph
• UnitDiskGraph

Contributing

Contributions are welcome!

Development Setup

git clone https://github.com/liujinguo/problemreductions
cd problemreductions
cargo build
cargo test

Running Tests

cargo test                    # Run all tests
cargo test --test integration # Integration tests only
cargo test --test reduction   # Reduction tests only

Code Coverage

cargo tarpaulin --skip-clean --ignore-tests

Documentation

cargo doc --open              # Rustdoc
mdbook serve                  # mdBook (requires mdbook installed)

Adding a New Problem

1. Create file in src/models/<category>/
2. Implement Problem trait
3. Optionally implement ConstraintSatisfactionProblem
4. Add tests
5. Export in mod.rs and prelude

Adding a New Reduction

1. Create file in src/rules/
2. Implement ReductionResult for the result type
3. Implement ReduceTo<Target> for Source
4. Add edge in ReductionGraph
5. Add tests
6. Export in mod.rs

Code Style

• Run cargo fmt before committing
• Run cargo clippy and fix warnings
• Add doc comments for public items
• Include examples in documentation