Corollary 14, p. 806 — either a node with in- and out-balls of radius 1/4n² of size ≥ 2n/3, or a directed cut of ratio cost O(W log n)
ProvedLeightonRao.Directed.corollary_14directed-graphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1region-growingsparsest-cut
Let be a directed network on nodes and a distance function with total weight . Put . Then either
- there is a node with and , or
- there is a nonempty proper whose directed cut has ratio cost
This is the dichotomy that drives Lemma 16.
Formalization Note The paper states option 2 as "ratio cost "; the explicit bound is the display computed in the proof on p. 806. Polynomial-time findability is not formalized: "we can find" is existence.
Preamble
import Mathlib import Definitions.Def_LeightonRao_Directed_Setting
Formal statement
namespace LeightonRao.Directed
/-- Leighton–Rao, Corollary 14, p. 806. With `Δ = 1/(4n²)`, either some node `v` has
`|𝒩^Δ_in(v)| ≥ 2n/3` and `|𝒩^Δ_out(v)| ≥ 2n/3`, or some directed cut has ratio cost at most
`8 W log₂ n / (Δ (n/6)(5n/6))` (the bound computed in the proof, `= (1152/5) W log₂ n`). -/
theorem corollary_14 {V : Type} [Fintype V] [DecidableEq V] (N : DiNetwork V)
(hn : 2 ≤ Fintype.card V) (d : V → V → ℝ) (hd : ∀ u v, 0 ≤ d u v) :
let n : ℝ := (Fintype.card V : ℝ)
let Δ : ℝ := 1 / (4 * n ^ 2)
(∃ v, 2 * n ≤ 3 * ((inBall N d v Δ).card : ℝ) ∧
2 * n ≤ 3 * ((outBall N d v Δ).card : ℝ)) ∨
(∃ U : Finset V, U.Nonempty ∧ Uᶜ.Nonempty ∧
diRatio N U ≤ 8 * diTotalWeight N d * Real.logb 2 n / (Δ * (n / 6) * (5 * n / 6))) := by sorry
end LeightonRao.Directed
Source
Leighton and Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46 (1999), p. 806, Corollary 14 and the display in its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.