Crate problemreductions

Crate problemreductions 

Source
Expand description

§Problem Reductions

A Rust library for reducing NP-hard problems.

This library 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

  • Problem Definitions: Implementations of 18+ NP-hard problems
  • Reduction Rules: Transform problems into equivalent problems
  • Solvers: Brute-force solver for testing and verification
  • Validation: Utilities to verify solution validity

§Example

use problemreductions::prelude::*;
use problemreductions::models::graph::IndependentSet;

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

§Satisfiability

  • SAT: Boolean satisfiability with CNF clauses
  • K-SAT: SAT restricted to k-literal clauses
  • CircuitSAT: Boolean circuit satisfiability
  • Factoring: Integer factorization

§Graph Problems

  • IndependentSet: Maximum weight independent set
  • MaximalIS: Maximal independent set
  • VertexCovering: Minimum weight vertex cover
  • DominatingSet: Minimum dominating set
  • Coloring: K-vertex coloring

§Set Problems

  • SetCovering: Minimum weight set cover
  • SetPacking: Maximum weight set packing

§Optimization Problems

  • MaxCut: Maximum cut on weighted graphs
  • SpinGlass: Ising model Hamiltonian
  • QUBO: Quadratic unconstrained binary optimization
  • Matching: Maximum weight matching

§Specialized Problems

  • Paintshop: Minimize color switches
  • BicliqueCover: Biclique cover on bipartite graphs
  • BMF: Boolean matrix factorization

Re-exports§

pub use error::ProblemError;
pub use error::Result;
pub use registry::ComplexityClass;
pub use registry::ProblemCategory;
pub use registry::ProblemInfo;
pub use solvers::BruteForce;
pub use solvers::Solver;
pub use traits::ConstraintSatisfactionProblem;
pub use traits::Problem;
pub use types::EnergyMode;
pub use types::LocalConstraint;
pub use types::LocalSolutionSize;
pub use types::ProblemSize;
pub use types::SolutionSize;

Modules§

config
Configuration utilities for problem solving.
error
Error types for the problemreductions library.
graph_types
Graph type markers for parametric problem modeling.
io
File I/O utilities for problem serialization.
models
Problem model implementations.
polynomial
Polynomial representation for reduction overhead.
prelude
Prelude module for convenient imports.
registry
Problem registry and metadata types.
rules
Reduction rules between NP-hard problems.
solvers
Solvers for computational problems.
testing
Testing utilities and macros for problem implementations.
topology
Graph topology types.
traits
Core traits for problem definitions.
truth_table
Truth table utilities for logic gadgets.
types
Common types used across the problemreductions library.

Macros§

complement_test
Generate tests for verifying complement relationships between problems.
declare_graph_subtype
Macro to declare both compile-time trait and runtime registration.
graph_problem_tests
Generate standard tests for a graph problem using the template.
poly
Convenience macro for building polynomials.
quick_problem_test
Quick test for a single problem instance.