Theorem 10.4 — fully dynamic APSP: approximation , amortized update time (corrected: degenerate factors)
OpenDecrNbhdCover.Supplement.theorem_10_4There are a constant and one deterministic program with the following property. The input is an -vertex graph that initially contains no edges and undergoes an online sequence of edge insertions and deletions, where every edge has an integer length , and a parameter . Let be the total number of edges that ever lie in and the maximum edge length. The values and are not known to the algorithm.
- A distance query returns an estimate with
in at most steps. 2. A shortest-path query with returns a (possibly non-simple) - path in of length at most , in at most steps, or correctly reports that no such path exists, in at most steps. 3. With the number of updates, the total time outside query windows is at most
This is the full version of the paper's Theorem 1.6: deterministic fully dynamic all-pairs shortest paths with constant approximation for constant and amortized update time . The paper derives it from Theorems 9.2 and 3.29.
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: abstract graphs, updates and answers → vertices and operations given as words; the -th inserted edge is edge ; a distance answer is or a rational; a path answer is "no such path" or a list of edge numbers; reason: a machine reads and writes words; relabeling changes no instance
- reading: "Let denote the total number of edges that ever lie in , and let denote the maximum edge-length; the values and are not known to the algorithm" → is the number of insertions and the largest inserted length of the whole operation sequence, which the program reads online; reason: every edge that ever lies in is inserted, since starts with no edges
- reading: "amortized update time … per update", and → the total time outside query windows, initialization included, is at most times the per-update bound, with the number of updates; query windows take at most and steps; reason: the meaning of amortized time over the whole sequence, and the explicit form of
- correction: the factors and of the amortized bound, and the multiplication by the number of updates → , and ; reason: the printed bound is when a factor vanishes. Counterexample meeting every assumption: a single insertion of an edge of length (, ) costs at least one step; with no update at all (, ) the run still reads and
import Mathlib import Definitions.Def_DecrNbhdCover_Supplement_FullyDynamic set_option autoImplicit false open DynConnWC open scoped ENNReal
namespace DecrNbhdCover.Supplement
/-- **Theorem 10.4 (Fully-Dynamic APSP).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.80-81 (PDF 84-85).
"Theorem 10.4 (Fully-Dynamic APSP) There is a deterministic algorithm that receives as input an n-vertex graph G that initially contains no edges, and that undergoes an online sequence of edge insertions and deletions, where every edge e has an integral length ℓG(e) > 0. The algorithm is additionally given a parameter 0 < ϵ < 1. Let m denote the total number of edges that ever lie in G, and let L denote the maximum edge-length; the values m and L are not known to the algorithm. The algorithm supports two types of queries: approximate distance query: given a pair u, v ∈V (G) of vertices, return a distance estimate du,v with distG(u, v) ≤du,v ≤2^{1/ poly(ϵ)} · distG(u, v), in time O(polylog(m)); and approximate shortest-path query: given a pair u, v ∈V (G) of distinct vertices, return a (possibly non-simple) u-v path P in G of length at most 2^{1/ poly(ϵ)}·distG(u, v) in time O(|E(P)| · polylog(m)), or correctly report that no such path exists, in time O(polylog(m)). The amortized update time of the algorithm is O(m^{O(ϵ)} · 2^{O(1/ poly(ϵ))} · log L) per update."
**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. Input words: `n`, then `ϵ` as a rational. `m` (the number of edges that ever lie in `G`, i.e. of insertions), `L` (the largest inserted length) and the number `k` of updates are those of the whole sequence. `2^{1/poly(ϵ)}` is `2^{C/ϵ^C}` for both queries; `polylog(m)` is `C·log₂(2+m)^C`; the amortized update time `X` means that the total time outside query windows, initialization included, is at most `max(1, k)·X`, with `X = C·max(1, m)^{Cϵ}·2^{C/ϵ^C}·log₂(2+L)`. The word size is every `W ≥ c₁⌈log₂(2 + largest input word)⌉ + ⌈(1/ϵ)^{c₁}⌉`. -/
theorem theorem_10_4 :
∃ (C c₁ : ℕ) (P : Program), NoRand P ∧
∀ (n : ℕ) (eps : ℚ), 0 < eps → eps < 1 →
∀ (W : ℕ) (σ : List FDOp), FDValid n σ → NoVertexUpd σ →
c₁ * Nat.clog 2 (2 + fdProtocol.inputMax (n :: ratWords eps) σ) + ⌈(1 / (eps : ℝ)) ^ c₁⌉₊ ≤ W →
RunsThrough W P (fdProtocol.blocks (n :: ratWords eps) σ) ∧
APSPQueries (fdProtocol.out W P (n :: ratWords eps) σ) (wTime W P (fdProtocol.blocks (n :: ratWords eps) σ)) n σ
(expEps C (eps : ℝ))
((C : ℝ) * lg (fdInsertions σ : ℝ) ^ C) ((C : ℝ) * lg (fdInsertions σ : ℝ) ^ C)
((C : ℝ) * lg (fdInsertions σ : ℝ) ^ C) ∧
(fdProtocol.updateTime W P (n :: ratWords eps) σ : ℝ) ≤
mx1 (fdK σ) * ((C : ℝ) * mx1 (fdInsertions σ) ^ ((C : ℝ) * (eps : ℝ)) * expEps C (eps : ℝ) *
lg (fdL σ : ℝ)) := by sorry
end DecrNbhdCover.Supplement