Theorem 3.26 — decremental ApproxBall: , , time
OpenDecrNbhdCover.Supplement.theorem_3_26deterministic-algorithmsdynamic-graph-algorithmsneighborhood-coverp2o-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 subset that undergoes an online sequence of vertex deletions, and parameters and . The program maintains a subset such that:
- At all times .
- For every it maintains a value with
- After initialization vertices may leave but none may join it, and as long as lies in the value does not decrease. Every change is reported.
- A query returns a path in from to a vertex of 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.3. It needs no degree bound, and the paper uses it for decremental single-source shortest paths (Theorem 10.1).
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
- reading: → ; reason: the explicit form of with the universal constant
Preamble
import Mathlib import Definitions.Def_DecrNbhdCover_Supplement_Ball set_option autoImplicit false open DynConnWC open scoped ENNReal
Formal statement
namespace DecrNbhdCover.Supplement
/-- **Theorem 3.26 (ApproxBall in decremental graphs).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.27-28 (PDF 31-32).
"Theorem 3.26 (ApproxBall in decremental graphs) 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 subset S ⊆V (G) of vertices that undergoes an online sequence of vertex deletions, and parameters 0 < ϵ < 1 and D > 0. The algorithm maintains a subset S′ ⊆V (G) of vertices, such that, at all times, BG(S, D/ϵ^2) ⊆S′ holds. Additionally, the algorithm maintains, for every vertex v ∈S′, a value d(v) ≤O(D/ϵ^2) with distG(v, S) ≤d(v) ≤(1 + ϵ)distG(v, S) + ϵ · D. Once the vertex set S′ is initialized, vertices may leave it but no new vertices may join it; every vertex deletion from S′ is explicitly reported by the algorithm. Additionally, for every vertex v ∈V (G), as long as v lies in S′, the value d(v) may not decrease, and every change in d(v) is reported by the algorithm. Lastly, the algorithm supports approximate shortest-path queries: given a vertex v ∈S′, return a path P in G connecting v to a vertex of S 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(ϵ))})."
**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. `d(v) ≤ O(D/ϵ²)` is `d(v) ≤ C·D/ϵ²`; `m^{1+O(ϵ)}` is `m^{1+Cϵ}`; `G` has `n ≥ 1` vertices. -/
theorem theorem_3_26 :
∃ (C c₁ : ℕ) (P : Program), NoRand P ∧
∀ I : DBallInput, I.Ok →
∀ (W : ℕ) (σ : List DBallOp),
c₁ * Nat.clog 2 (2 + dballProtocol.inputMax I.words σ) + ⌈(1 / (I.eps : ℝ)) ^ c₁⌉₊ ≤ W →
I.Valid W P σ → DBallHolds 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 3.26, pp.27–28 (PDF 31–32); proof C.8