Redesign reduction-path selection around final composed overhead

[isPANN]

Background

A reduction path transforms one problem into another through one or more registered reductions. Each reduction declares symbolic output-size overhead, and a path's final overhead is obtained by composing those expressions from the source to the target.

The current scalar path API (PathCostFn, Minimize, MinimizeSteps, CustomCost, CostLabel, and find_cheapest_path*) instead assigns a numeric cost to every edge and adds those costs along the path. This answers the wrong question. Users care about the overhead of the final target problem; intermediate problem sizes are neither a common unit nor part of the optimization objective. Hop count is also not a criterion for path optimality.

For example, suppose a direct path produces a final target with 100 variables, while a two-edge path produces an intermediate problem with 60 items and a final target with 50 variables. Final-overhead selection must choose the two-edge path. Summing edge outputs scores it as 110 and incorrectly chooses the direct path merely because it is shorter.

Objective

Replace accumulated scalar edge-cost path selection with final-state ordering:

• A path's objective value is its final composed target overhead, not a sum over edges.
• The default instance-free result is the Pareto front across all final target size fields.
• minimize:<field> compares only that field in the final composed target overhead.
• For a concrete source instance, measured selection compares only the final constructed target size (or requested final field), never the sum of intermediate sizes.
• Hop count may be reported as metadata, but must not affect Pareto membership or optimality ranking.
• Witness/aggregate/Turing requirements and solver/backend availability are feasibility filters, not costs.
• Exact versus bounded search is a completeness policy, not an objective.

Remove the obsolete scalar-cost contract rather than preserving it behind adapters or compatibility wrappers. This includes evaluating whether PathCostFn, CustomCost, Minimize*, CostLabel, find_cheapest_path*, and the CLI/MCP minimize-steps option should be deleted and their callers migrated to direct final-overhead APIs.

Interface (Input → Output)

Instance-free search

• In: exact source and target variants, required reduction capability, completeness policy, and optionally a final target field.
• Out without a field: every nondominated path under the vector of composed symbolic overhead expressions for the final target fields.
• Out with minimize:<field>: path or tied paths minimizing the composed symbolic growth of that final target field.

Instance-aware search

• In: a concrete source instance, feasible target set, required capability/backend constraints, completeness policy, and optionally a final target field.
• Out: path whose constructed final target has the least measured final size (or least value of the requested final field).

Equal-overhead routes may be deterministically ordered for stable output, but hop count must not change which routes are optimal.

Technical recommendations

These are non-binding implementation suggestions:

• Keep symbolic composition (GrowthLabel/asymptotic_front) and concrete execution (MeasuredLabel/measured search) as the two direct domains.
• Give minimize-field selection a terminal comparison over the composed/final label; do not express it as an edge callback.
• Keep feasibility filtering and SearchMode outside the ordering rule.
• Replace current internal callers that genuinely need any feasible route with an explicitly named feasibility/path-discovery operation, rather than MinimizeSteps.
• Delete superseded scalar labels, cost implementations, exports, CLI/MCP parsing, and synthetic arbitrary-score regressions after callers are migrated.

Verification

Add a focused semantic test runnable with:

cargo test reduction_path_final_overhead

The test must construct a small graph with these routes:

1. S → T, final target field x = 100.
2. S → M → T, intermediate field value 60, final target field x = 50.
3. A route whose final vector is strictly dominated by another route.
4. Two routes with mutually incomparable final vectors, such as (x = 10, y = 100) and (x = 100, y = 10).

Expected observable results:

• Final-field minimization selects S → M → T because 50 < 100, despite its extra hop and despite 60 + 50 > 100.
• Default vector ordering returns both incomparable vectors on the Pareto front.
• The strictly dominated final vector is absent.
• Reordering edges or changing only the number of intermediate hops does not alter the optimal final-overhead set.

The first assertion is the negative control: an implementation that retains accumulated edge cost or shortest-path ranking will select S → T and fail. The dominated-vector assertion prevents an implementation from passing by returning every path.

Run the full regression suite afterward:

cargo test
cargo test --manifest-path problemreductions-cli/Cargo.toml

Compatibility impact

This is intentionally a breaking replacement of the legacy library path-cost API and the CLI/MCP minimize-steps behavior. Do not retain arbitrary edge-cost callbacks unless a separate, real cumulative quantity with consistent units is specified in a future requirement.

Out of scope

• Inventing a generic objective/adapter framework for hypothetical future costs.
• Treating solver capability or backend preference as a numeric weight.
• Preserving accumulated edge-cost behavior for backward compatibility.