Theorem 3.24 — emulator for decremental graphs: , time
OpenDecrNbhdCover.Supplement.theorem_3_24deterministic-algorithmsdynamic-graph-algorithmsneighborhood-coverp2o-gran-per-chapterp2o-plan-bookp2o-v1shortest-paths
There is a constant such that for every 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, and parameters and with . The program maintains a dynamic graph with positive edge lengths such that:
- at all times, and all edge lengths of are integer multiples of a value with that is fixed at initialization.
- The number of edges that ever lie in is at most .
- At all times, for all ,
- Given a (possibly non-simple) path in between distinct whose inner vertices all lie in , the program returns a (possibly non-simple) path in from to with and , in at most steps.
- The total update time is at most .
This is the paper's emulator theorem, the full version of its Theorem 1.2: a sparse graph with coarse edge lengths that preserves the distances of a decremental graph up to a factor and an additive .
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: "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: → ; reason: a two-sided bound with a universal constant
- reading: the number of edges that ever lie in "is bounded by " → at most , with a leading constant; reason: the proof (C.6) bounds the number by a constant multiple of plus and absorbs the constant; without the leading constant the bound is not what C.6 proves for small
- reading: → ; reason: the explicit form of and with the universal constant
- encoding: a dynamic graph whose lengths are integral multiples of a fixed → is reported once as a positive rational, and is reported edge by edge with positive integer multipliers; may change by any vertex or edge insertion or deletion; reason: a value reported once cannot change, and integer multipliers make every length a multiple of it; the theorem does not restrict the updates of
Preamble
import Mathlib import Definitions.Def_DecrNbhdCover_Supplement_Emulator set_option autoImplicit false open DynConnWC open scoped ENNReal
Formal statement
namespace DecrNbhdCover.Supplement
/-- **Theorem 3.24 (Emulator for decremental graphs).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.27 (PDF 31).
"Theorem 3.24 (Emulator for 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, and parameters 0 < ϵ < 1 and 0 < d < D, such that D > 4d·2^{1/ϵ^{c′}}, for a large enough universal constant c′. The algorithm maintains a dynamic graph H with positive edge lengths, such that V (G) ⊆V (H) holds at all times, and, throughout the algorithm, all edge lengths in H are integral multiples of a value d∗= Θ(d) that remains fixed throughout the algorithm. Moreover, the total number of edges that ever lie in H is bounded by m^{1+O(ϵ)}, and, at all times, for every pair x, y ∈V (G) of vertices, distG(x, y) ≤distH(x, y) ≤(1 + ϵ)distG(x, y) + ϵD holds. Additionally, there is a deterministic algorithm that, given a (possibly non-simple) path P in H connecting a pair x, y ∈V (G) of distinct vertices, such that all inner vertices of P lie in V (H) \ V (G), computes a (possibly non-simple) path P′ in G connecting x to y, with ℓG(P′) ≤ℓH(P) and |E(P′)| ≥Ω(|E(P)|/ poly log m), 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. "a large enough universal constant c′" is read as `∃ c₀, ∀ c′ ≥ c₀`. `d* = Θ(d)` is `d/C ≤ d* ≤ C·d`; `Ω(|E(P)|/poly log m)` is `|E(P)| ≤ C·log₂(2+m)^C·|E(P′)|`; `m^{1+O(ϵ)}` (edges ever in `H`) is `C·m^{1+Cϵ}` (the proof in C.6, p.107, absorbs a constant factor into it). `G` has `n ≥ 1` vertices. `H` is reported with integral multipliers of the reported `d*`, so all its lengths are integral multiples of `d*` (see the definition module). The word size is every `W ≥ c₁⌈log₂(2 + largest input word)⌉ + ⌈(1/ϵ)^{c₁}⌉`. -/
theorem theorem_3_24 :
∃ c₀ : ℕ, ∀ c', c₀ ≤ c' →
∃ (C c₁ : ℕ) (P : Program), NoRand P ∧
∀ I : EmuInput, I.Ok c' →
∀ (W : ℕ) (σ : List EmuOp),
c₁ * Nat.clog 2 (2 + emuProtocol.inputMax I.words σ) + ⌈(1 / (I.eps : ℝ)) ^ c₁⌉₊ ≤ W →
I.Valid W P σ → EmuHolds 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.24, p.27 (PDF 31); proof C.6