Theorem 9.3 — one recursive level of the APSP reduction: , total time (corrected: )
OpenDecrNbhdCover.Supplement.theorem_9_3deterministic-algorithmsdynamic-graph-algorithmsneighborhood-coverp2o-correctedp2o-gran-per-chapterp2o-plan-bookp2o-v1shortest-paths
There 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 integers with and a graph that initially has no edges or vertices and undergoes an online sequence of at most updates. Each update is an edge insertion, an edge deletion, an insertion of an isolated vertex, or a deletion of an isolated vertex, and every inserted edge has an integer length in . Let
- 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 update time is at most
The time of includes the time of every instance of that it runs. This theorem is the single level of the recursion by which the paper proves Theorem 9.2.
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: edge lengths up to and distances up to times them need bits, and the oracle is only required to work at word sizes large enough for its own input and bounds
- reading: , , , and "total update time" → , , , and the time outside query windows, initialization included; reason: the explicit forms with the constant ; here , so and differ by a factor of at most
- correction: the factor of the total update time → ; reason: Definition 9.1 allows for small , and the printed bound is then . Counterexample meeting every assumption: an oracle whose bound function has (possible, since on edges its time bound is still positive), , and no update; the run must still read
- encoding: , and a graph with "no edges or vertices" → the ceiling of for naturals, which forces ; the session starts from the empty vertex set, and an inserted vertex carries a number chosen by the update; reason: p.13: logarithms are to base 2
- 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
Preamble
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
Formal statement
namespace DecrNbhdCover.Supplement
/-- **Theorem 9.3 (one recursive level).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.68 (PDF 72).
"Theorem 9.3 Let α, s, T : N →N be nondecreasing functions. There exists a deterministic algorithm, whose input consists of integers M, b, h with 1 ≤h ≤b ≤⌈log M⌉, and a graph G that initially has no edges or vertices, and undergoes an online sequence of at most ⌈M^{h/b}⌉ updates. Each update is an edge insertion, an edge deletion, an insertion of an isolated vertex, or a deletion of an isolated vertex, and every inserted edge has an integral length in [1, M^{2(b+1−h)}]. Furthermore, the algorithm is given black-box access to an (α, s, T)-neighborhood-cover algorithm A. 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 ≤βh · distG(u, v), where βh = (7α(M))^{3h}, in time O(h · polylog(M)); 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 βh·distG(u, v), in time O(h^2·|E(P)|·polylog(M)), or correctly report that no such path exists, in time O(h · polylog(M)). The total update time of the algorithm is O(M^{(h+2)/b} · T(M) · (s(M) · log M)^{O(h)})."
**Formalization Note.** The paper names no machine. *Black-box access* is as for Theorem 9.2: the algorithm is a reduction `R` (a `rand`-free program of the word RAM of the mission extended by the oracle instructions `spawn`, `send`, `avail`, `recv` of the definition module), chosen before the oracle program `A` and its constant `C_A`; `R` reaches `A` only by sending input words to instances of `A` and receiving the words they write, and every step of every instance counts in the time of `R`. The constants of the conclusion are `K(C_A)` for one map `K` fixed before `α, s, T`, `R` and `A`. `⌈log M⌉` is `Nat.clog 2 M`, so `M ≥ 2`; the graph starts with no vertices and no edges; an inserted vertex carries a number chosen by the update, and the `j`-th inserted edge is edge `j`. `polylog(M)` is `K·log₂(2+M)^K`; `O(h²·|E(P)|·polylog M)` is `K·h²·log₂(2+M)^K·(|E(P)| + 1)`; a query window's time is bounded per answer and excluded from the total update time, which includes the initialization; `T(M)` is `max(1, T(M))` (Definition 9.1 allows `T(M) = 0` for small `M`, and the printed bound is then `0`, although the run reads its input); `log M` in the time bound is `log₂(2+M)`. Input words: `M`, `b`, `h`. The word size is every `W ≥ K(C_A)·(b+1)·⌈log₂(2 + largest input word + α(M) + s(M) + T(M))⌉`, shared by `R` and the instances of `A`. -/
theorem theorem_9_3 :
∃ K : ℕ → ℕ, ∀ (α s T : ℕ → ℕ), Monotone α → Monotone s → Monotone T →
∃ R : OProgram, ONoRand R ∧
∀ (CA : ℕ) (A : Program), IsNCAlgorithm α s T CA A →
∀ (M b h : ℕ), 1 ≤ h → h ≤ b → b ≤ Nat.clog 2 M →
∀ (W : ℕ) (σ : List FDOp), FDValid 0 σ →
fdK σ ≤ ⌈(M : ℝ) ^ ((h : ℝ) / (b : ℝ))⌉₊ →
(∀ u ∈ fdUpdates σ, ∀ x y ℓ, u = .ins x y ℓ → 1 ≤ ℓ ∧ ℓ ≤ M ^ (2 * (b + 1 - h))) →
K CA * (b + 1) * Nat.clog 2 (2 + fdProtocol.inputMax [M, b, h] σ + α M + s M + T M) ≤ W →
ORunsThrough W R A (fdProtocol.blocks [M, b, h] σ) ∧
APSPQueries (oWOutput W R A (fdProtocol.blocks [M, b, h] σ)) (oWTime W R A (fdProtocol.blocks [M, b, h] σ)) 0 σ
((7 * (α M : ℝ)) ^ (3 * h))
((K CA : ℝ) * (h : ℝ) * lg (M : ℝ) ^ K CA) ((K CA : ℝ) * (h : ℝ) ^ 2 * lg (M : ℝ) ^ K CA)
((K CA : ℝ) * (h : ℝ) * lg (M : ℝ) ^ K CA) ∧
(fdUpdateTime (oWTime W R A (fdProtocol.blocks [M, b, h] σ)) σ : ℝ) ≤
(K CA : ℝ) * (M : ℝ) ^ (((h : ℝ) + 2) / (b : ℝ)) * mx1 (T M) *
((s M : ℝ) * lg (M : ℝ)) ^ (K CA * h) := 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 9.3, p.68 (PDF 72); Definition 9.1, p.67 (PDF 71); proof §9.2