Theorem 10.1 — decremental -approximate SSSP in time (corrected: )
OpenDecrNbhdCover.Supplement.theorem_10_1deterministic-algorithmsdynamic-graph-algorithmsneighborhood-coverp2o-correctedp2o-gran-per-chapterp2o-plan-bookp2o-v1shortest-paths
There are a constant and one deterministic program with the following property. The input is an -vertex, -edge graph with integer lengths that undergoes an online sequence of edge deletions, a source vertex , and a parameter . Let be the maximum edge length.
- The program maintains, for every vertex , a value with
- The value never decreases, and every change to is reported.
- A query with returns a - path in of length at most , in at most steps.
- The total update time is at most
This is the full version of the paper's Theorem 1.5: a deterministic decremental single-source shortest-paths algorithm with near-linear total update time, obtained from Theorem 3.26.
Differences from the source:
- reading: the algorithm is "deterministic", and no machine is named → one program of the published word RAM
DynConnWC.Programwith norandinstruction, at unit cost per instruction, run as an online session of word blocks; reason: a running time needs a machine, and the paper counts ordinary word operations; this is the reading of the published base goal - reading: , , → one constant chosen with the program, before every input: for and , an exponent for , and for the factor hidden by ; reason: p.81: the hidden constants are universal; p.13: hides factors polylogarithmic in the initial and
- encoding: no word size is stated → every word size , with chosen with the program; reason: input numbers must fit in words; the time budget contains while a RAM addresses only cells
- encoding: real parameters → rationals given by numerator and denominator; reason: a machine reads words
- encoding: "total update time", and query time → the steps outside query windows, initialization included; a query window takes at most steps; reason: a query changes nothing and has its own bound; the covers the empty path
- encoding: "path" → a walk, given by the list of its edge numbers; reason: p.72: "Recall that paths may be non-simple unless mentioned otherwise"
- encoding: abstract graphs, updates and reports → vertices with , edges numbered by input order, updates and reports given as words and folded into a record in which an illegal report makes the run fail; reason: a machine reads and writes words; relabeling changes no instance, and an empty vertex set has nothing to state
- correction: the factor of the total update time → ; reason: at the printed factor is and the bound becomes . Counterexample meeting every assumption: unit lengths () and parallel or distinct edges; reading the input words alone takes more than steps for large
- encoding: a value that may be , maintained for every vertex, with every change reported → every estimate is before any report; a report sets to a rational or to ; "never decreases" is stated between consecutive moments with the largest value; reason: the theorem speaks of , so is a value; a disconnected vertex has
Preamble
import Mathlib import Definitions.Def_DecrNbhdCover_Supplement_SSSP set_option autoImplicit false open DynConnWC open scoped ENNReal
Formal statement
namespace DecrNbhdCover.Supplement
/-- **Theorem 10.1 (Decremental SSSP).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.77 (PDF 81).
"Theorem 10.1 (Decremental SSSP) There is a deterministic algorithm, whose input consists of an n-vertex and m-edge graph G with integral lengths ℓG(e) > 0 on its edges e ∈E(G), that undergoes an online sequence of edge deletions, a source vertex s ∈V (G), and a parameter 0 < ϵ < 1. The algorithm maintains, for every vertex v ∈V (G), a value d(v) with distG(v, s) ≤d(v) ≤(1 + ϵ)distG(v, s). Over the course of the algorithm, the value d(v) may not decrease, and every change to d(v) is reported by the algorithm. Lastly, the algorithm supports approximate shortest-path queries: given a vertex v ∈V (G) with d(v) < ∞, return a v-s path P in G of length at most d(v), in time ˜O(|E(P)|). The total update time of the algorithm is O(n + m^{1+O(ϵ)} · 2^{O(1/ poly(ϵ))} · log L), where L denotes the maximum edge-length."
**Formalization Note.** One program of the published word RAM `DynConnWC.Program` with no `rand` instruction; the constants are chosen before every input; `Õ(·)` hides `C·log₂(2+n+m)^C` in the initial `n, m` (p.13); a query window's time is bounded per answer and excluded from the total update time. `L` is the largest edge length of the input graph and `log L` is `log₂(2 + L)` (at `L = 1` the printed factor is `0`); `m^{1+O(ϵ)}` is `m^{1+Cϵ}`; `2^{O(1/poly(ϵ))}` is `2^{C/ϵ^C}`. -/
theorem theorem_10_1 :
∃ (C c₁ : ℕ) (P : Program), NoRand P ∧
∀ I : SSSPInput, I.Ok →
∀ (W : ℕ) (σ : List SSSPOp),
c₁ * Nat.clog 2 (2 + ssspProtocol.inputMax I.words σ) + ⌈(1 / (I.eps : ℝ)) ^ c₁⌉₊ ≤ W →
I.Valid W P σ → SSSPHolds C W P I σ := by sorry
end DecrNbhdCover.Supplement
Source
Chuzhoy, Mosenzon, A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems (STOC 2027 submission, preprint, sha256 4278ef58f7a6a1c6a6ac1cde172bfd04b0f0652af498f3f8d09c6e94c1c352df), Theorem 10.1, p.77 (PDF 81); proof §10.1