Theorem 10.7 — decremental tree cover: dominating tree embeddings with stretch , time (corrected: degenerate logarithms)
OpenDecrNbhdCover.Supplement.theorem_10_7deterministic-algorithmsdynamic-graph-algorithmsneighborhood-coverp2o-correctedp2o-gran-per-chapterp2o-plan-bookp2o-v1shortest-paths
There are a function with , 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, where is the maximum edge length. The program maintains a collection of
graphs with positive integer edge lengths such that, at all times:
- for all , the graph is a dominating tree embedding of : a forest with and for all ;
- for every pair there is an index with
The total update time is at most .
This is the full version of the paper's Theorem 1.7. A tree cover lets distance computations in be replaced by computations in a few trees.
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
- 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: and → one function with , chosen with the program before every input, the bound , and ; reason: one algorithm whose exponent tends to ; the proof uses Theorem 3.31, whose parameter depends on the input size alone
- reading: , for "some index" → at each moment and for each pair there is an index , which may depend on the pair and the moment, with ; reason: p.13 for ; the theorem quantifies the index after the pair
- correction: and the factor of the stretch → and ; reason: the printed bounds vanish at degenerate inputs. Counterexample meeting every assumption: the one-vertex graph (, ) would need trees, but the pair needs an index ; and for unit lengths () and two adjacent vertices the stretch bound would be
- encoding: a maintained collection of graphs → is reported once, and each is a reported dynamic graph that may change by any vertex or edge insertion or deletion; reason: the theorem does not restrict how the change; a tree that is not needed can be the edgeless graph on , which is a dominating tree embedding
Preamble
import Mathlib import Definitions.Def_DecrNbhdCover_Supplement_TreeCover set_option autoImplicit false open DynConnWC open scoped ENNReal open Filter Topology
Formal statement
namespace DecrNbhdCover.Supplement
/-- **Theorem 10.7 (Decremental Tree Cover).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.82 (PDF 86).
"Theorem 10.7 (Decremental Tree Cover) 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, where L denotes the maximum edge-length. The algorithm maintains a collection T = {T1, . . . , Tk} of k = O(log(n)·log(L·n)) graphs, with integral lengths ℓT (e) > 0 on the edges of each T ∈T , that satisfy the following properties: for all 1 ≤i ≤k, the graph Ti is a dominating tree embedding of G; and, for every pair u, v ∈V (G) of vertices, there exists some index 1 ≤i ≤k, such that distTi(u, v) ≤ ˜O (distG(u, v) · log L). The total update time of the algorithm is O((m + n)^{1+o(1)} · polylog(L))."
**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. `o(1)` is one function `f` of `m + n` with `f → 0`, chosen before every input. `k = O(log(n)·log(L·n))` is `k ≤ C·log₂(2+n)·log₂(2+L·n)` (at `n = 1` the printed bound is `0`, although at least one tree is needed); `Õ(distG(u, v)·log L)` is `C·log₂(2+n+m)^C·log₂(2+L)·distG(u, v)`; `polylog(L)` is `log₂(2+L)^C`. `G` has `n ≥ 1` vertices. The word size is every `W ≥ c₁⌈log₂(2 + largest input word)⌉`. -/
theorem theorem_10_7 :
∃ f : ℕ → ℝ, Tendsto f atTop (𝓝 0) ∧
∃ (C c₁ : ℕ) (P : Program), NoRand P ∧
∀ I : TreeInput, I.Ok →
∀ (W : ℕ) (σ : List ℕ),
c₁ * Nat.clog 2 (2 + treeProtocol.inputMax I.words σ) ≤ W →
I.Valid σ → TreeHolds f 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 10.7 and Definition 10.6, p.82 (PDF 86); proof §10.3