Home | Publications | Projects | News | CV GitHub · Google Scholar · Email

Problem Reductions

A Rust library and CLI (pred) for NP-hard problem definitions, reductions, and routing across solvers

Overview

problem-reductions is a Rust infrastructure that catalogs 100+ computationally hard problems and 200+ reduction rules between them, exposed through a CLI tool called pred. Built with agentic coding workflows, it answers two practical questions:

  1. Given an NP-hard problem A, what is the most efficient target problem B to reduce it to so we can reuse an existing solver?
  2. How broadly can a solver designed for problem B be reused across the rest of the problem landscape?

The reduction graph is transitive: registering a new solver for a single node immediately makes it available to every problem connected to it.

Reduction graph across 100+ NP-hard problems

Figure 1 from the paper — a portion of the reduction graph. Nodes are problem types and directed edges are reductions. Registering a solver for any node propagates along outgoing paths to reachable problems.


The pred CLI

The command-line tool provides a unified interface to:


Reduction Graph

At the core is a registry that stores problems as nodes and reductions as directed edges. A path-search routine finds the sequence of reductions from any source problem to a problem with a registered solver, composing per-edge forward/backward transformations to recover the original solution.

Quality-detection tools flag isolated or unreachable problems so coverage can be improved systematically.


Scale and Engineering


Inspirations

Package Ecosystem
ProblemReductions.jl Julia
UnitDiskMapping.jl Julia
qubogen Python


Last updated November 1, 2026.