Theorem 3.31 — -PLDD in decremental graphs: path-reporting, approximation , time
OpenDecrNbhdCover.Supplement.theorem_3_31deterministic-algorithmsdynamic-graph-algorithmsneighborhood-coverp2o-gran-per-chapterp2o-plan-bookp2o-v1shortest-paths
There are a function with , a constant and one deterministic program that is a path-reporting algorithm for the -PLDD problem (Definition 3.30) with approximation factor
and total update time at most
In detail, the input is an -vertex, -edge graph with integer lengths under an online sequence of edge deletions, and integers . The program maintains partitions of such that:
- for every cluster , at all times, the induced subgraph has diameter at most ;
- for every vertex , the number of indices such that at some time was not -covered by is at most , where is -covered by if some cluster of contains ;
- after initialization the partitions change only by cluster splitting, and the program lists all vertices of each new cluster;
- a query with returns a - path of length at most , in at most steps.
This is the full version of the paper's Theorem 1.4. Compared with the neighborhood cover of Theorem 3.29 it gives partitions, a bound on the strong diameter, and coverage by all but of the partitions; the paper uses it for its decremental tree cover (Theorem 10.7).
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: "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: → one function with , chosen with the program before every input, and the bound ; reason: the proof (§8) fixes as a function of alone, so one algorithm has an exponent that tends to
- reading: approximation factor → , the same in the diameter clause and in the query clause; reason: p.13: hides factors polylogarithmic in and ; Definition 3.30 uses one
- reading: Definition 3.30: the number of indices is "bounded by " → at most ; reason: the explicit form with the universal constant; at the single vertex is always covered, so both forms give the count
- encoding: partitions that change by cluster splitting, with the vertices of listed → clusters with ids, created only in the initialization window; afterwards the only legal report is a split listing the vertices moved to a new id; a cluster emptied by a split stays in the record; reason: this is the update the definition allows; an empty cluster affects no clause
- encoding: the clauses hold at all times, and the covering clause counts the indices for which was not -covered "at any time" → the moments after the initialization window and after the window of each operation; reason: the partitions are observable only through the reports, and the reports of one window take effect together. This is the convention of the published base mission
Preamble
import Mathlib import Definitions.Def_DecrNbhdCover_Supplement_PLDD set_option autoImplicit false open DynConnWC open scoped ENNReal open Filter Topology
Formal statement
namespace DecrNbhdCover.Supplement
/-- **Theorem 3.31 (k-PLDD in decremental graphs).** Chuzhoy, Mosenzon, *A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems* (STOC 2027 submission, sha256 4278ef58…), p.30 (PDF 34).
"Theorem 3.31 (k-PLDD in decremental graphs) There is a deterministic path-reporting algorithm for the k-PLDD problem that achieves approximation factor ˜O(k), and has total update time: O((n + m^{1+o(1)}) · k)."
**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` with `f → 0`, chosen before every input (the proof in §8 fixes `ϵ` as a function of `m`). The approximation factor `Õ(k)` is `α = C·k·log₂(2+n+m)^C`, used both for the strong diameter and for the query paths; `O(log n)` of Definition 3.30 is `C·log₂(2+n)` (at `n = 1` both readings force the count `0`, since the one vertex is always covered); `m^{1+o(1)}` is `m^{1+f(m)}`; `G` has `n ≥ 1` vertices. The word size is every `W ≥ c₁⌈log₂(2 + largest input word)⌉`. -/
theorem theorem_3_31 :
∃ f : ℕ → ℝ, Tendsto f atTop (𝓝 0) ∧
∃ (C c₁ : ℕ) (P : Program), NoRand P ∧
∀ I : PLDDInput, I.Ok →
∀ (W : ℕ) (σ : List PLDDOp),
c₁ * Nat.clog 2 (2 + (plddProtocol I.n I.k).inputMax I.words σ) ≤ W →
I.Valid W P σ → PLDDHolds 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 3.31, p.30 (PDF 34); Definition 3.30, pp.29–30 (PDF 33–34); proof §8