You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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).
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
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.
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.
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 innum_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 Twithout--sizereturns 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.extendsubstitutes the edge's overhead expressions into the label;dominatesis componentwise (all fields ≤, one strict). A label with anUnknownfield is dominated by any fully-known label (undecidable paths rank last — the honest ranking).pred path <S> <T>(no--size) prints the Pareto front — typically 1–3 paths — each withO(...)per target size field; paths withUnknowngrowth are annotated explicitly. Output ordered by (hops, lexicographic node names).--sizebehavior (single best path) is unchanged from Replace scalar Dijkstra with measured Pareto label-setting search (concrete-instance mode) #1076.find_pathtool returns the same front in its JSON shape (structuredGrowthserialization from Add growth domain (src/growth.rs): growth terms, antichain, symbolic dominance #1075).Technical recommendations (non-binding)
GrowthLabel::extendfollows from the monotonicity axiom — add it to the property tests if cheap.ReductionGraphconstructor from an explicit edge list (if not already feasible) makes the negative control below clean; keep it#[cfg(test)].Verification
pred path KSatisfiability QUBO(no--size) prints ≥ 1 path, each step chain annotated with a normalizedO(...)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.cargo testgreen, 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 costingO(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.