Research: multi-variable shortest path over polynomials for optimal reductions

[GiggleLiu]

Problem Statement

Finding the most efficient reduction path from problem A to problem B is not a standard shortest path problem — it is a multi-variable shortest path over polynomials.

Why standard shortest path doesn't work

Each problem type has different size metrics:

Problem	Size Metrics
MaximumIndependentSet	num_vertices, num_edges
Satisfiability	num_vars, num_clauses, num_literals
QUBO	num_variables, num_terms
SpinGlass	num_spins, num_interactions

A reduction from problem A to problem B maps A's size metrics to B's size metrics via polynomials. For example, SAT → MIS maps:

num_vertices = num_literals
num_edges    = num_literals²

When we compose reductions along a path, the end-to-end overhead is a composition of polynomials — still polynomial, but in the original source variables.

The core difficulty

To compare two reduction paths, we need to compare their composed overhead polynomials. But these are multivariate polynomials — a path may produce O(n²) vertices but O(n) edges, while another produces O(n) vertices but O(n³) edges. There is no total ordering.

This makes the problem a multi-objective shortest path where:

• Edge weights are polynomial transformations (not scalars)
• Composition is polynomial substitution (not addition)
• Comparison requires Pareto dominance or a user-specified preference

Current implementation

The codebase already has the building blocks:

1. Polynomial overhead representation (src/polynomial.rs, src/rules/registry.rs):

   • ReductionOverhead maps each target size field to a Polynomial over source size variables
   • ReductionOverhead::compose() performs symbolic polynomial substitution

2. Cost-based path finding (src/rules/graph.rs, src/rules/cost.rs):

   • find_cheapest_path() uses Dijkstra with a PathCostFn trait
   • Current cost functions evaluate at a fixed input size (e.g., Minimize("num_vertices"))
   • This works for a specific instance but doesn't give a general answer

3. Path overhead composition (ReductionGraph::compose_path_overhead()):

   • Can compose all edge overheads along a path into a single end-to-end polynomial mapping

What's missing

The current approach evaluates polynomials at a concrete input size and runs scalar Dijkstra. This has limitations:

1. Instance-dependent: The optimal path may change for different input sizes
2. Single-objective: Minimize("num_vertices") ignores edge count growth
3. No symbolic comparison: Cannot determine if path A is asymptotically better than path B

Research Directions

1. Pareto-optimal path enumeration

Find all Pareto-optimal reduction paths where no other path dominates on all size metrics simultaneously. This gives users the full trade-off frontier.

2. Polynomial dominance

Define a partial order on multivariate polynomials (e.g., path A dominates path B if every output polynomial of A is asymptotically ≤ B's). Use this for symbolic path pruning.

3. Weighted scalarization

Let users specify a weight vector over target size metrics (e.g., "I care 2x more about vertices than edges") and scalarize the multi-objective cost into a single polynomial for standard shortest path.

4. Asymptotic regime analysis

Different paths may be optimal in different asymptotic regimes. Characterize the crossover points where one path becomes cheaper than another.

Related

• Polynomial representation: src/polynomial.rs
• Reduction overhead: src/rules/registry.rs (ReductionOverhead)
• Path finding: src/rules/graph.rs (find_cheapest_path)
• Cost functions: src/rules/cost.rs (PathCostFn trait)

[isPANN]

This research question now has a concrete design: growth-class labels (antichains of dominant monomials) with Pareto label-setting search — see docs/design/symbolic-growth-domain.md. Will be closed by #1080 (asymptotic search + Pareto front CLI), with #1081 unifying the dominance order.