Theorem 2.1 — betweenness reduction: whp
ProvedBFAlmostLinear.theorem_2_1graph-algorithmsnegative-weightsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithmsshortest-paths
Let be a weighted graph on vertices with frozen flags, a set of vertices, and hop bounds . Let contain each vertex of independently with probability . There is an absolute exponent , and for every a constant , such that with probability at least over : for every potential that fixes and all families () with whenever , ,
This is the first of the paper's two new tools: after a reweighting that fixes a random sample, the forward and backward searches have almost linear total size.
Differences from the source:
- generalization: one hop bound → a pair ; reason: Lemma 4.6's proof (p.18) applies the result to ; is the printed form.
- generalization: the negative vertices → any set of vertices; reason: the proof only uses the sampling of from .
- encoding: → with absolute and depending on ; reason: footnote 1, p.1.
- encoding: "with high probability" → probability for every ; reason: footnote 2, p.1.
- encoding: frozen-flag convention → hypothesis
Frozen; reason: §1.1, p.2.
Preamble
import Mathlib import Definitions.Def_BFAlmostLinear_WGraph import Definitions.Def_BFAlmostLinear_sampleMass
Formal statement
namespace BFAlmostLinear
open Classical in
/-- **Theorem 2.1**, p.5. "Let U ⊆ N be a random sample where each vertex in N is sampled with probability 1/b. With
high probability over the randomness of U, the following holds. Consider any potential function ϕ that fixes U, and
for each negative vertex r ∈ N, consider any V^in_r, V^out_r ⊆ V such that for all s ∈ V^in_r, t ∈ V^out_r, we have
d^h_ϕ(s, r) + d^h_ϕ(r, t) < 0. Then, Σ_{r∈N} min{|V^in_r|, |V^out_r|} ≤ Õ(nb)."
Hair, Li, Li, Zhang, *Bellman-Ford in Almost-Linear Time*, STOC 2027 submission (manuscript sha256
873b9acb…), Theorem 2.1, p.5.
**Formalization Note.** `Õ(nb)` is `K n b (log n)^a`, where the exponent `a` is absolute and `K` depends on the
probability exponent `c`. Generalized to a hop pair `(h₁, h₂)`, with `N` any set of vertices (finding F5 of the plan:
Lemma 4.6's proof needs `h₁ ≠ h₂`). The families `V^in`, `V^out` are quantified inside the good event. -/
theorem theorem_2_1 :
∃ a : ℕ, ∀ c : ℝ, 0 < c → ∃ K : ℝ, 0 < K ∧
∀ (V E : Type) [Fintype V] [Fintype E] (G : WGraph V E) (N : Finset V) (b : ℝ) (h₁ h₂ : ℕ),
G.Frozen → 1 ≤ b →
1 - (Fintype.card V : ℝ) ^ (-c) ≤
goodMass N b fun U =>
∀ ϕ : V → ℝ, G.Fixes h₁ h₂ U ϕ → ∀ Vin Vout : V → Finset V,
(∀ r ∈ N, ∀ s ∈ Vin r, ∀ t ∈ Vout r, G.InX h₁ h₂ ϕ s r t) →
((∑ r ∈ N, min (Vin r).card (Vout r).card : ℕ) : ℝ) ≤
K * (Fintype.card V : ℝ) * b * Real.log (Fintype.card V) ^ a := by sorry
end BFAlmostLinear
Source
Hair, Li, Li, Zhang, Bellman-Ford in Almost-Linear Time, STOC 2027 submission (manuscript sha256 873b9acb…), Theorem 2.1, p.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.