Theorem 3.27 — MaintainCluster in decremental graphs: bit with a far pair, paths of length in , time
OpenDecrNbhdCover.Supplement.theorem_3_27deterministic-algorithmsdynamic-graph-algorithmsneighborhood-coverp2o-gran-per-chapterp2o-plan-bookp2o-v1shortest-paths
There are a constant and one deterministic program with the following property. The input is a graph with integer lengths that initially has vertices and edges and undergoes an online sequence of edge deletions and vertex deletions, and parameters and . The updates arrive in batches. The first batch arrives at the beginning, and all later batches are non-empty.
- After each batch the program returns a bit , and if it also returns two vertices with .
- A short-path query with returns a - path in of length at most
in at most steps. A query may be asked only if the program returned after the most recent batch, and not before is processed. 3. The total update time is at most .
This variant of the weak MaintainCluster problem needs no emulator and no degree bound, and answers with paths in . The paper uses it in its -PLDD algorithm (Theorem 3.31).
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
- encoding: the bit and the pair are "returned" → the window of a batch outputs exactly
1, or0, v, v′with current vertices and in the current graph, where the distance may be ; reason: the published format of the weak MaintainCluster problem; nothing is required of the bit beyond what the theorem states
Preamble
import Mathlib import Definitions.Def_DecrNbhdCover_Supplement_Cluster set_option autoImplicit false open DynConnWC open scoped ENNReal
Formal statement
namespace DecrNbhdCover.Supplement
/-- **Theorem 3.27 (MaintainCluster in decremental graphs).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.28 (PDF 32).
"Theorem 3.27 (MaintainCluster in decremental graphs) There is a deterministic algorithm, whose input consists of a graph G with integral lengths ℓG(e) > 0 on its edges e ∈E(G) that initially has n vertices and m edges, and that undergoes an online sequence of edge deletions and vertex deletions, as well as parameters 0 < ϵ < 1 and D > 0. The updates to graph G arrive in batches, where the first batch, B0 = ∅, arrives immediately at the beginning of the algorithm; all subsequent batches must be non-empty. After each batch B of updates, the algorithm returns a bit gB ∈{0, 1}, and, if gB = 0, it also returns a pair v, v′ ∈V (G) of vertices with distG(v, v′) > D. Lastly, the algorithm supports short-path queries: given a pair v, v′ ∈V (G) of vertices, return a v-v′ path P of length at most 2^{1/ poly(ϵ)} · D in G, in time ˜O (|E(P)|). A short-path query may only be asked if the algorithm returned gB = 1 following the most recent batch B of updates to G, and it cannot be asked before the first batch B0 is processed. 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. The path bound `2^{1/poly(ϵ)}·D` is `2^{C/ϵ^C}·D`; `m^{1+O(ϵ)}` is `m^{1+Cϵ}`; `G` has `n ≥ 1` vertices. The theorem does not require the bit `1` when the diameter is small, and none is required here. -/
theorem theorem_3_27 :
∃ (C c₁ : ℕ) (P : Program), NoRand P ∧
∀ I : CBInput, I.Ok →
∀ (W : ℕ) (σ : List CBOp),
c₁ * Nat.clog 2 (2 + cbProtocol.inputMax I.words σ) + ⌈(1 / (I.eps : ℝ)) ^ c₁⌉₊ ≤ W →
I.Valid W P σ → CBHolds 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.27, p.28 (PDF 32); proof C.9