Lemma 5, p. 799 — |T| ≥ 2n/3 and Σ_{u∉T} d(T, u) ≥ 1/2n give a cut of ratio cost ≤ 6W
ProvedLeightonRao.Uniform.lemma_5graph-cutgraph-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparsest-cut
Let be a connected network on nodes and a distance function with total weight . Suppose satisfies and
where is the shortest-path distance from . Then there is a nonempty proper subset with
This handles the case of Corollary 4 in which a large component of small radius exists.
Formalization Note The page states the conclusion as "ratio cost "; the constant is the one computed in the proof on p. 800 (). Connectivity is the paper's standing assumption (p. 789) and makes the graph distances well defined; makes nonempty and a proper cut exist.
Preamble
import Definitions.Def_LeightonRao_Uniform_Dual set_option autoImplicit false open scoped BigOperators
Formal statement
namespace LeightonRao.Uniform
/-- Lemma 5, p. 799, with the proof's explicit factor `6`. -/
theorem lemma_5 {V : Type} [Fintype V] [DecidableEq V]
(N : Network V) (hn : 2 ≤ Fintype.card V) (hconn : IsConnectedNet N)
(d : V → V → ℝ) (hd : IsDistanceFunction d)
(T : Finset V) (hT : 2 * (Fintype.card V : ℝ) ≤ 3 * (T.card : ℝ))
(hsum : 1 / (2 * (Fintype.card V : ℝ)) ≤ ∑ u ∈ Tᶜ, distFrom N d T u) :
∃ U : Finset V, U.Nonempty ∧ Uᶜ.Nonempty ∧
ratioCost N U ≤ 6 * totalWeight N d := by sorry
end LeightonRao.Uniform
Source
Leighton and Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46 (1999), p. 799, Lemma 5 (constant 6 from its proof, p. 800)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.