§6.1 rounding bound — Bernstein's scaled graph G_i has positive integer weights and every ≤h-hop path of weight in [2^i, 2^{i+1}] has G_i-weight ≤ ⌈4h/ε⌉
ProvedDecrNearAddAPSP.W2.section_6_1_roundingapaspdynamic-shortest-pathshopsetsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rounding
Let be a weighted graph with positive integer weights, , an integer hop parameter, an integer, and . The scaled graph keeps the edges of weight at most , rounds each kept weight up to the nearest integer multiple of and divides by , so the edge gets weight . Then:
- every edge of has a positive integer weight: whenever ;
- for every path of (any walk, simple or not) with at most hops and ,
This is what lets an ES-tree on run to depth independently of (Bernstein's rounding, used by SCALE in §7).
Differences from the source:
- reading: 0 < ε (the scaled graph is defined for the paper's ε) → 0 < ε < 1; reason: the standing range of the §6 tools (Theorem 7, Lemma B.2 p. 97); the bound fails for large ε, where h edges each rounded to 1 exceed ⌈4h/ε⌉
- generalization: for each 0 ≤ i ≤ log(nW_max) → for every i ∈ ℕ; reason: the claim holds for each scale separately; the paper's range is a subset, so the statement specializes to it
- encoding: every edge in G_i has a positive integer weight → 0 < ⌈w(e)/α_i⌉ in ℤ for every edge with w(e) ≤ 2^{i+1}; reason: the ceiling is an integer by type; the kept edges are those of weight ≤ 2^{i+1}
- generalization: any path p of at most h hops in G → every walk of G (simple or not) with at most h edges; reason: p. 6 defines a path as a sequence of edges; every edge of p has weight ≤ w(p) ≤ 2^{i+1} and is kept, and the statement specializes to simple paths
- reading: a graph G = (V, E) (Lemma statement); §5 p. 25: "each edge e ∈ E has a positive weight w(e) > 0" → G.PosWeights (every edge weight ≥ 1); reason: standing assumption of the weighted sections (§5 p. 25), with integer weights (p. 6)
Preamble
import Mathlib import Definitions.Def_DecrNearAddAPSP_W2_Graphs
Formal statement
namespace DecrNearAddAPSP.W2
/-- **§6.1 rounding bound** (p. 36). Let `G` have positive integer weights, `0 < ε < 1`, `h ≥ 1` a
hop parameter, `i ∈ ℕ`, and `α_i = ε·2^i/h`. In the scaled graph `G_i` (edges of weight at most
`2^{i+1}`, weight `w` mapped to `⌈w/α_i⌉`) every edge has a positive integer weight, and every path
`p` of `G` (any walk, simple or not) with at most `h` hops and `2^i ≤ w(p) ≤ 2^{i+1}` has `w_{G_i}(p) ≤ ⌈4h/ε⌉`. -/
theorem section_6_1_rounding {n : ℕ} (G : WGraph (Fin n)) (hpos : G.PosWeights) (ε : ℝ)
(hε0 : 0 < ε) (hε1 : ε < 1) (h i : ℕ) (hh : 1 ≤ h) :
(∀ e ∈ G.adj.edgeSet, G.wt e ≤ 2 ^ (i + 1) → 0 < scaledWeight ε h i (G.wt e)) ∧
(∀ (u v : Fin n) (p : G.adj.Walk u v), p.length ≤ h →
2 ^ i ≤ G.walkWeight p → G.walkWeight p ≤ 2 ^ (i + 1) →
scaledWalkWeight G ε h i p ≤ ⌈4 * (h : ℝ) / ε⌉) := by sorry
end DecrNearAddAPSP.W2
Source
Koveshi, Roditty, Sapir, First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted Graphs, arXiv:2611.04635 (PDF sha256 6bb2b230…), p. 36, §6.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.