General-domain adapter for a charged polynomial-weight decremental solver
ProvedDecrAlmostLinearSSSP.Decremental.general_domain_adapterSuppose one deterministic scalar arithmetic-RAM program handles all valid inputs with at least two vertices, integer weights bounded by the square of the size bound, and accuracy strictly between the reciprocal size bound and one. Assume that it explicitly maintains simultaneous approximate source distances and exact unreachability, terminates after every legal deletion prefix, has a uniform constant query bound, and has total charged maintenance work
where and is positive and subpolynomial. Then there is one deterministic scalar arithmetic-RAM program for the full input domain, including singleton graphs, arbitrarily small positive real accuracy, and arbitrary positive integer weight bound . It has a uniform constant query bound and satisfies
The new program and constants may depend on the supplied polynomial-weight solver but are chosen before every full-domain graph and deletion stream. This is the general-domain reduction on p.4 and its footnote, expressed as a reusable implication between charged online-program guarantees. It retains initialization, exact infinity, stored-array queries and all adapter work.
Formalization Note The exponent two suffices for the mission's rounded instances: internal accuracy is , size is padded to , and weights are rounded with . These explicit wrapper choices are from the mission definitions; the paper's reduction is unnumbered. The small-accuracy and singleton branches remain implementation obligations, and no successful-run or output-accuracy certificate is supplied as input.
import Definitions.Def_DecrAlmostLinearSSSP_Decremental_Adapters set_option autoImplicit false open scoped ENNReal NNReal
namespace DecrAlmostLinearSSSP.Decremental
theorem general_domain_adapter
(p : Program) (C : ℝ) (a : ℕ → ℝ) (queryBound : ℕ)
(hC : 0 < C) (hquery : 0 < queryBound) (ha : Subpolynomial a)
(hpoly : ∀ i : Input, i.Valid → 2 ≤ i.n → i.W ≤ i.size ^ 2 →
1 / (i.size : ℝ) < i.accuracy → i.accuracy < 1 →
Maintains p C a queryBound false i) :
∃ (p' : Program) (C' : ℝ) (a' : ℕ → ℝ) (queryBound' : ℕ),
0 < C' ∧ 0 < queryBound' ∧ Subpolynomial a' ∧
∀ i : Input, i.Valid → Maintains p' C' a' queryBound' true i := by sorry
end DecrAlmostLinearSSSP.Decremental