Lemma 3.2 — Implemented dynamic cuts on nonempty vertex domains
OpenDecrAlmostLinearSSSP.Decremental.NonemptyCut.dynamic_cut_interfaceFix a natural exponent bounding the numerical range. There is one finite deterministic scalar arithmetic-RAM program, chosen before the graph size, detector threshold and update stream, together with a positive constant and positive subpolynomial functions .
For each size bound , the quality satisfies
The program initializes on every nonempty physical undirected multigraph with , positive active capacities in , total demand zero and vertex demands bounded in absolute value by . The zero-seminorm directions are exactly the constant vectors. A supplied positive capacity bound covers the initial active capacities and is at most .
The program terminates after initialization and every legal insertion, deletion, paired demand change, ratio request, cut toggle or potential query. It maintains the actual physical updates and an implicit potential initially zero. For nonzero demand, a returned cut and numbers satisfy
A legal toggle adds to the maintained potential, where . For any threshold , every active edge whose capacity-weighted endpoint difference changes by at least since insertion or its last report is explicitly reported. Baselines update exactly on reported identifiers. Queries return the maintained potential at the requested vertex.
If toggles and total operations have completed and identifiers have been emitted, then
Initialization, all operation bodies and all output writes are actual finite RAM executions; no accurate cut oracle or successful-execution certificate is an input. This is the implemented cut interface required by Lemma 3.2 and the repair algorithm in §3.2.
Formalization Note The semantic view is required only when . This preserves every admitted graph instance while avoiding the impossible unrestricted request for a graph with and . All original physical, toggle, ratio, baseline, detector and work guarantees are retained.
import Definitions.Def_DecrAlmostLinearSSSP_NonemptyCutProtocol set_option autoImplicit false open scoped ENNReal NNReal
namespace DecrAlmostLinearSSSP.Decremental.NonemptyCut
theorem dynamic_cut_interface :
∀ exponent : ℕ, ∃ (impl : Implementation) (K h Γ a : ℕ → ℝ) (C : ℝ),
0 < C ∧ Subpolynomial K ∧ Subpolynomial h ∧ Subpolynomial Γ ∧ Subpolynomial a ∧
(∀ m, 32 ≤ K m ∧ K m ≤ Real.rpow 2
(C * Real.rpow (Real.log (max 2 m : ℕ)) (5 / 6 : ℝ) *
max 1 (Real.log (Real.log (max 2 m : ℕ))))) ∧
∀ m ξ, 0 < ξ → Implements impl m exponent (K m) (h m) (Γ m)
(C * m * a m) ξ := by sorry
end DecrAlmostLinearSSSP.Decremental.NonemptyCut