Skip to content

Add instance-free asymptotic path search and Pareto-front CLI output #1080

Description

@isPANN

Background

With the Pareto label-search kernel in place (#1076) and the growth domain available (#1075), path search can answer the question the library exists for but currently cannot: "between problem class S and problem class T, which reduction paths are asymptotically best?" — with no concrete instance sizes given. Because asymptotic growth over multiple size variables is a partial order, the answer is a Pareto front: possibly several mutually incomparable optimal paths (one better in num_vertices, another in num_edges), all of which should be reported honestly. This closes the 2-year-old research issue #15, which anticipated exactly this problem ("multi-variable shortest path over polynomials").

Full design (shared overview for this batch): docs/design/symbolic-growth-domain.md, sections M3/M4.

Objective

Add the asymptotic label domain to the search kernel and surface it: pred path S T without --size returns the Pareto front of asymptotically optimal paths, each annotated with its composed Big-O per size field. Closes #15 (comment with a link to the design doc when closing).

Interface (Input → Output)

  • GrowthLabel: BTreeMap<&'static str, Growth> mapping each size field of the current node to its growth in the source problem's variables. extend substitutes the edge's overhead expressions into the label; dominates is componentwise (all fields ≤, one strict). A label with an Unknown field is dominated by any fully-known label (undecidable paths rank last — the honest ranking).
  • CLI: pred path <S> <T> (no --size) prints the Pareto front — typically 1–3 paths — each with O(...) per target size field; paths with Unknown growth are annotated explicitly. Output ordered by (hops, lexicographic node names). --size behavior (single best path) is unchanged from Replace scalar Dijkstra with measured Pareto label-setting search (concrete-instance mode) #1076.
  • MCP find_path tool returns the same front in its JSON shape (structured Growth serialization from Add growth domain (src/growth.rs): growth terms, antichain, symbolic dominance #1075).

Technical recommendations (non-binding)

  • Isotonicity of GrowthLabel::extend follows from the monotonicity axiom — add it to the property tests if cheap.
  • A test-only ReductionGraph constructor from an explicit edge list (if not already feasible) makes the negative control below clean; keep it #[cfg(test)].

Verification

  1. pred path KSatisfiability QUBO (no --size) prints ≥ 1 path, each step chain annotated with a normalized O(...) per size field of QUBO, and the full output is byte-identical across two consecutive runs and across Linux/macOS CI (golden file) — which proves the asymptotic mode works and is deterministic.
  2. cargo test green, including the existing instance-mode tests from Replace scalar Dijkstra with measured Pareto label-setting search (concrete-instance mode) #1076 (no regression).

Negative control (the front is real, not a single-answer shortcut): a unit test builds a small graph (test-only constructor) with two S→T paths whose composed growths are incomparable — path A costing O(n^2) vertices / O(m) edges, path B costing O(n) vertices / O(m^2) edges — and asserts the returned front contains both paths. An implementation that scalarizes or picks one representative fails this test.

Dependencies

Depends on #1075 and #1076. Milestone: Symbolic Growth Domain & Pareto Search. Closes #15.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    Status
    No status

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions