Lemma 19, p. 808 — partition with edge and distance radii
ProvedLeightonRao.ShortPaths.lemma_19graph-partitionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1short-path-flowsparsest-cut
Let be a connected capacitated graph on vertices, with total capacity . Let be a nonnegative symmetric edge-length function with positive total weight , and let . There is a partition of into components such that each component has one center and paths within that component witnessing both radii, and
The partition supplies the simultaneous path-length and distance control used in the short-path result.
Formalization Note The paper's standing connectivity convention is explicit. The added condition makes its division by meaningful; at , Lean's real division would incorrectly give radius zero. A single internal walk witnesses both radii.
Preamble
import Mathlib import Definitions.Def_LeightonRao_ShortPaths_Setting
Formal statement
namespace LeightonRao.ShortPaths
/-- Lemma 19, p. 808. The positivity of W makes the paper's radius ΔC/W meaningful. -/
theorem lemma_19 {V : Type} [Fintype V] [DecidableEq V]
(N : Network V) (hn : 2 ≤ Fintype.card V) (hconn : IsConnectedNet N)
(d : V → V → ℝ) (hd : IsDistanceFunction d)
(Δ : ℝ) (hΔ : 0 < Δ) (hW : 0 < totalWeight N d) :
∃ P : Finpartition (Finset.univ : Finset V),
(∀ S ∈ P.parts, HasRadii N d S (Δ * totalCap N / totalWeight N d) Δ) ∧
crossCap N P ≤ 4 * totalWeight N d *
Real.logb 2 (Fintype.card V : ℝ) / Δ := by sorry
end LeightonRao.ShortPaths
Source
Leighton and Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46 (1999), p. 808, Lemma 19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.