Theorem 9.2 — fully dynamic APSP from a black-box neighborhood cover: , amortized time (corrected: degenerate factors)
OpenDecrNbhdCover.Supplement.theorem_9_2There is a function such that for all nondecreasing functions there is one deterministic reduction with the following property, for every -neighborhood-cover algorithm with constant (Definition 9.1), where has black-box access to and .
The input is an integer and an -vertex graph with positive integer edge lengths that initially contains no edges and undergoes an online sequence of edge insertions and deletions. Let be the total number of updates, the largest length of an edge ever inserted, and
which is the paper's except when and (see the last difference below). The values and are not known to the algorithm.
- A distance query returns a value with , in at most steps.
- 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.
- The total time outside query windows is at most , where
The time of includes the time of every instance of that it runs. This is the paper's black-box reduction from fully dynamic all-pairs shortest paths to decremental neighborhood cover; with Theorem 3.29 as the oracle it gives Theorem 10.4.
Differences from the source:
- reading: "The algorithm is additionally given black-box access to an -neighborhood-cover algorithm"; black-box access is not defined → the algorithm is a reduction on the oracle word RAM of the definition item: is fixed before the oracle program , can create instances of , send them input words and receive the words they write, and every step of every instance counts in the time of ; reason: this is what a black-box reduction is: one program for every oracle, which reaches the oracle only through its input and output; Definition 9.1 makes the algorithm report and precisely so that such a user can learn them
- reading: the constants of and in the conclusion, and those of Definition 9.1 → the oracle meets Definition 9.1 with its own constant , and the conclusion holds with the constant for one function fixed before , the reduction and the oracle; reason: p.81: "The constants hidden in the bounds of Theorem 9.2 depend only on the constants hidden in the time bounds that Definition 9.1 requires from the neighborhood-cover algorithm"
- reading: the algorithm is "deterministic", and no machine is named → the reduction and the oracle are programs with no
randinstruction on the word RAM of the mission, at unit cost per instruction; reason: a running time needs a machine; this is the reading of the published base goal - encoding: no word size is stated → every word size , shared by the reduction and the instances of the oracle; reason: the reduction handles numbers up to times a distance, which needs bits, and the oracle is only required to work at word sizes large enough for its own input and bounds
- reading: "Let denote the total number of updates … the values and are not known to the algorithm" → , and are computed from the whole operation sequence, which the reduction reads online; reason: this is how a quantity of the whole run that the algorithm does not know enters a guarantee
- reading: "amortized update time" → the total time outside query windows, initialization included, is at most ; reason: the meaning of amortized time over the whole sequence; the proof (F.1) charges the work, including restarts, to the updates
- reading: and → and ; reason: the explicit form with the constant ; at the literal is
- correction: the factors , , , , of the amortized bound → , , , , ; reason: the printed bound is whenever one factor vanishes. Counterexample meeting every assumption: a single insertion of an edge of length (, , so ) costs at least one step; likewise Definition 9.1 allows for small and does not constrain at , where the run still reads and
- 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
- encoding: in the bounds → ; reason: the same number whenever an -neighborhood-cover algorithm exists and , because Definition 9.1 forces for every (a short-path query between the two ends of an edge needs a path of positive length). The two differ only at with , where the graph has no edges and the printed bound reads for , which is undefined on the page and equals in the extended reals of Lean, so the literal statement would be false there
import Mathlib import Definitions.Def_DecrNbhdCover_Supplement_FullyDynamic import Definitions.Def_DecrNbhdCover_Supplement_NCAlgorithm import Definitions.Def_DecrNbhdCover_Supplement_Oracle set_option autoImplicit false open DynConnWC open scoped ENNReal
namespace DecrNbhdCover.Supplement
/-- **Theorem 9.2 (Fully dynamic APSP from decremental neighborhood cover).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.67-68 (PDF 71-72).
"Theorem 9.2 (Fully dynamic APSP from decremental neighborhood cover) Let α, s, T : N →N be any nondecreasing functions. There exists a deterministic algorithm, whose input consists of an integral parameter b ≥1 and an n-vertex graph G with positive integral edge lengths that initially contains no edges, and that undergoes an online sequence of updates consisting of edge insertions and deletions. The algorithm is additionally given black-box access to an (α, s, T)-neighborhood-cover algorithm. Let k denote the total number of updates, let L denote the maximum edge-length of edges that are ever inserted into G, and let β = 3·(7α(6k))^{3b}; the values k and L are not known to the algorithm. The algorithm supports the following queries: approximate distance queries: given a pair u, v ∈V (G) of vertices, return a value d with distG(u, v) ≤d ≤β · distG(u, v), in time polylog(k); and approximate shortest-path queries: 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 β · distG(u, v), in time O(|E(P)| · polylog(k)), or correctly report that no such path exists, in time polylog(k). The amortized update time of the algorithm is O(k^{2/b} · T(6k) · (s(6k) · log k)^{O(b)} · log L)."
**Formalization Note.** The paper names no machine. *Black-box access.* The algorithm is a reduction `R`: a program of the word RAM of the mission (`DynConnWC.Program`, no `rand`) extended by the oracle instructions `spawn`, `send`, `avail`, `recv` of the definition module, run against an oracle program `A`. `R` is chosen before `A` and before the constant `C_A` of `A`, it can create instances of `A`, send them input words and receive the words they write, and nothing else of `A` reaches it; every step of every instance counts in the time of `R`. So one reduction serves every `(α, s, T)`-neighborhood-cover algorithm, as the page says (`R` may depend on `α, s, T`, which the page fixes first). An `(α, s, T)`-neighborhood-cover algorithm is a `rand`-free program meeting Definition 9.1 with its own constant `C_A` for the bounds `Õ(·)`, `O(·)` of that definition. The constants of the conclusion are `K(C_A)` for one map `K` fixed before `α, s, T`, `R` and `A`: they depend on the oracle only through `C_A`. *Bounds.* `k`, `L` are the number of updates and the largest inserted length of the whole sequence, so `β = 3·(7α(6k))^{3b}` is computed from the whole sequence; it is written `3·(7·max(1, α(6k)))^{3b}`, which is the same number whenever an `(α, s, T)`-neighborhood-cover algorithm exists and `k ≥ 1` (Definition 9.1 forces `α(m) ≥ 1` for `m ≥ 1`), and differs only at `k = 0` with `α(0) = 0`, where the graph has no edges and the printed bound `d ≤ β·distG(u, v)` reads `d ≤ 0·∞` for `u ≠ v`; `polylog(k)` is `K·log₂(2+k)^K`; a query window's time is bounded per answer and excluded from the update time; a path answer with `|E(P)|` edges takes at most `K·log₂(2+k)^K·(|E(P)| + 1)` steps. The amortized update time `X` means: the total time outside query windows, initialization included, is at most `max(1, k)·X`, with `X = K·max(1,k)^{2/b}·max(1, T(6k))·(max(1, s(6k))·log₂(2+k))^{K·b}·log₂(2+L)`: each `max` and each `log₂(2+·)` replaces a printed factor that vanishes at `k = 0`, at `T(6k) = 0`, at `s(0) = 0`, at `k = 1` or at `L = 1`, where the run still reads its input (Definition 9.1 allows `T(x) = 0` for small `x`, and constrains `s(0)` not at all). Input words: `n`, `b`. The word size is every `W ≥ K(C_A)·(b+1)·⌈log₂(2 + largest input word + k + α(6k) + s(6k) + T(6k))⌉`, shared by `R` and the instances of `A`. -/
theorem theorem_9_2 :
∃ K : ℕ → ℕ, ∀ (α s T : ℕ → ℕ), Monotone α → Monotone s → Monotone T →
∃ R : OProgram, ONoRand R ∧
∀ (CA : ℕ) (A : Program), IsNCAlgorithm α s T CA A →
∀ (n b : ℕ), 1 ≤ b →
∀ (W : ℕ) (σ : List FDOp), FDValid n σ → NoVertexUpd σ →
K CA * (b + 1) * Nat.clog 2 (2 + fdProtocol.inputMax [n, b] σ + fdK σ +
α (6 * fdK σ) + s (6 * fdK σ) + T (6 * fdK σ)) ≤ W →
ORunsThrough W R A (fdProtocol.blocks [n, b] σ) ∧
APSPQueries (oWOutput W R A (fdProtocol.blocks [n, b] σ)) (oWTime W R A (fdProtocol.blocks [n, b] σ)) n σ
(3 * (7 * mx1 (α (6 * fdK σ))) ^ (3 * b))
((K CA : ℝ) * lg (fdK σ : ℝ) ^ K CA) ((K CA : ℝ) * lg (fdK σ : ℝ) ^ K CA)
((K CA : ℝ) * lg (fdK σ : ℝ) ^ K CA) ∧
(fdUpdateTime (oWTime W R A (fdProtocol.blocks [n, b] σ)) σ : ℝ) ≤
mx1 (fdK σ) * ((K CA : ℝ) * mx1 (fdK σ) ^ ((2 : ℝ) / (b : ℝ)) * mx1 (T (6 * fdK σ)) *
(mx1 (s (6 * fdK σ)) * lg (fdK σ : ℝ)) ^ (K CA * b) * lg (fdL σ : ℝ)) := by sorry
end DecrNbhdCover.Supplement