General-weight adapter above the exact-recomputation threshold
ProvedDecrAlmostLinearSSSP.Decremental.normal_domain_sssp_adapterAssume one fixed deterministic scalar RAM program maintains approximate source distances on valid inputs with at least two vertices, weights bounded by the square of the size bound, and accuracy strictly between and . Suppose its total charged maintenance work is at most , where and is positive and subpolynomial.
Then a fixed deterministic scalar RAM adapter maintains the full distance array for every valid input with , arbitrary integer weight bound , and . For a positive constant and positive subpolynomial function , its charged work satisfies
The adapter terminates after initialization and every legal deletion prefix, maintains simultaneous multiplicative accuracy and exact unreachability, and answers a stored-array query in nine charged instructions. The program and bounds are uniform over all input parameters and streams. This isolates the general-weight reduction needed to extend the polynomial-weight theorem to the full domain.
import Mathlib import Definitions.Def_DecrAlmostLinearSSSP_Decremental_Adapters set_option autoImplicit false open scoped ENNReal NNReal open DecrAlmostLinearSSSP.Decremental
theorem DecrAlmostLinearSSSP.Decremental.normal_domain_sssp_adapter
(p : Program) (C : ℝ) (a : ℕ → ℝ) (queryBound : ℕ)
(hC : 0 < C) (ha : Subpolynomial a)
(hpoly : ∀ x : Input, x.Valid → 2 ≤ x.n → x.W ≤ x.size^2 →
1/(x.size : ℝ) < x.accuracy → x.accuracy < 1 → Maintains p C a queryBound false x) :
∃ (host : Program) (D : ℝ) (b : ℕ → ℝ), 0 < D ∧ Subpolynomial b ∧
∀ i : Input, i.Valid → 2 ≤ i.n → 1/(i.size : ℝ) < i.accuracy → Maintains host D b 9 true i := by sorry