Corollary 4, pp. 798–799 — a component of radius 1/2n² with ≥ 2n/3 nodes, or a cut of ratio cost ≤ 36W log n
ProvedLeightonRao.Uniform.corollary_4graph-cutlow-diameter-decompositionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparsest-cut
Let be a network on nodes and a distance function with total weight . Then at least one of the following holds:
- there is a set of at least nodes with radius at most ;
- there is a nonempty proper subset whose ratio cost satisfies
Corollary 4 applies Lemma 3 with ; it is the case split on which Lemma 6 is built.
Formalization Note The page states case (2) as "ratio cost "; the constant is the one computed in the proof on p. 799 (). "Find a component" is stated as the existence of a vertex set with the stated size and radius; Lemma 6 uses only these two properties. is assumed because a one-node graph has no proper cut. Algorithmic content ("we can find") is not formalized.
Preamble
import Definitions.Def_LeightonRao_Uniform_Dual set_option autoImplicit false open scoped BigOperators
Formal statement
namespace LeightonRao.Uniform
/-- Corollary 4, pp. 798–799, with the proof's explicit factor `36`. -/
theorem corollary_4 {V : Type} [Fintype V] [DecidableEq V]
(N : Network V) (hn : 2 ≤ Fintype.card V)
(d : V → V → ℝ) (hd : IsDistanceFunction d) :
(∃ T : Finset V,
2 * (Fintype.card V : ℝ) ≤ 3 * (T.card : ℝ) ∧
HasRadiusLE N d T (1 / (2 * (Fintype.card V : ℝ) ^ 2))) ∨
(∃ U : Finset V, U.Nonempty ∧ Uᶜ.Nonempty ∧
ratioCost N U ≤ 36 * totalWeight N d * Real.logb 2 (Fintype.card V : ℝ)) := 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), pp. 798–799, Corollary 4 (constant 36 from its proof, p. 799)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.