Theorem 3.25 — strong ApproxBall in time (corrected: )
OpenDecrNbhdCover.Supplement.theorem_3_25There is a constant such that for every there are a constant and one deterministic program that solves the strong ApproxBall problem (Definition 3.14) with parameter , with total update time at most
In detail, the input is a decremental graph (edge and vertex deletions) with vertices initially and maximum degree at most , a decremental set , and an integer with . The program maintains a decremental set with and, for , a value with that never decreases while . Every change is reported. A query returns a path in from to a vertex of of length at most , in steps, where is the initial number of edges.
The strong problem needs no emulator in its input. The paper obtains it from the weak ApproxBall problem and its emulator algorithm, and uses it for 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
- reading: Definition 3.14: "for a large enough universal constant " → , with the program and allowed to depend on ; reason: the usual meaning of "large enough"; the same reading as the published Theorem 3.28
- reading: the theorem says "an algorithm", not "a deterministic algorithm" → a program with no
randinstruction; reason: p.1: all algorithms in the paper are deterministic, and the weak problem's Theorem 3.15 says so explicitly - correction: the factor → ; reason: at the printed bound is . Counterexample meeting every assumption: a graph with vertices and no edges, so maximum degree , with and any admissible ; the run must still read its input, so its time is positive
- encoding: a decremental graph and a decremental subset → one operation deletes an edge of , or deletes a vertex of with its edges (the vertex then also leaves ), or deletes a vertex from ; reason: must hold after every update, so a vertex deleted from cannot stay in . A sequence that first deletes it from and then from is allowed as well, so no instance of the page is lost
import Mathlib import Definitions.Def_DecrNbhdCover_Supplement_Ball set_option autoImplicit false open DynConnWC open scoped ENNReal
namespace DecrNbhdCover.Supplement
/-- **Theorem 3.25 (strong ApproxBall).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.27 (PDF 31).
"Theorem 3.25 There is an algorithm for the strong ApproxBall problem with total update time O(n^{1+O(ϵ)} · µ^{O(1)} · 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. Definition 3.14's "large enough universal constant c" is read as `∃ c₀, ∀ c ≥ c₀`, as for the published Theorem 3.28. The theorem does not repeat "deterministic", but Definition 3.14 is stated for deterministic algorithms and p.1 says all algorithms of the paper are, so the program has no `rand`. The time bound `O(n^{1+O(ϵ)}·µ^{O(1)}·2^{O(1/poly(ϵ))})` is `C·n^{1+Cϵ}·max(1, µ)^C·2^{C/ϵ^C}`: at `µ = 0` (an edgeless graph, which the definition allows) the printed factor `µ^{O(1)}` is `0`, although the run reads its input. `n ≥ 1`. -/
theorem theorem_3_25 :
∃ c₀ : ℕ, ∀ c, c₀ ≤ c →
∃ (C c₁ : ℕ) (P : Program), NoRand P ∧
∀ I : SBallInput, I.Ok c →
∀ (W : ℕ) (σ : List SBallOp),
c₁ * Nat.clog 2 (2 + sballProtocol.inputMax I.words σ) + ⌈(1 / (I.eps : ℝ)) ^ c₁⌉₊ ≤ W →
I.Valid W P σ → SBallHolds C W P I σ := by sorry
end DecrNbhdCover.Supplement