Corollary 2.8 — weighted betweenness reduction: whp
ProvedBFAlmostLinear.corollary_2_8graph-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, , hop bounds , and with total weight . 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 for , ,
The vertex weights let the searches of §4.2 charge their cost to degrees and counters.
Differences from the source:
- generalization: one hop bound → a pair ; reason: Lemma 4.6's proof (p.18) applies this corollary to .
- generalization: the negative vertices → any set of vertices; reason: the proof only uses the sampling of from .
- encoding: , "with high probability" → with probability ; reason: footnotes 1–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
/-- **Corollary 2.8**, p.10. "Consider a non-negative weight λ(v) on every vertex v in the graph. Let
Λ = Σ_{v∈V} λ(v) denote the total weight. 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∈V^in_r} λ(v), Σ_{v∈V^out_r} λ(v)} ≤ Õ(Λb)."
Hair, Li, Li, Zhang, *Bellman-Ford in Almost-Linear Time*, STOC 2027 submission (manuscript sha256
873b9acb…), Corollary 2.8, p.10.
**Formalization Note.** `λ` comes before `U`: the proof's auxiliary graph depends on it, and the good event may depend
on it, as printed. `Õ(Λb)` is `K Λ b (log n)^a`, as in Theorem 2.1. `Λ = 0` is included. Generalized to `(h₁, h₂)`, with
`N` any set of vertices. -/
theorem corollary_2_8 :
∃ a : ℕ, ∀ c : ℝ, 0 < c → ∃ K : ℝ, 0 < K ∧
∀ (V E : Type) [Fintype V] [Fintype E] (G : WGraph V E) (N : Finset V) (b : ℝ) (h₁ h₂ : ℕ)
(lam : V → ℝ),
G.Frozen → 1 ≤ b → (∀ v, 0 ≤ lam v) →
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 (∑ v ∈ Vin r, lam v) (∑ v ∈ Vout r, lam v) ≤
K * (∑ v, lam 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…), Corollary 2.8, p.10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.