Lemma 15, p. 806 — a set T with |T| ≥ 2n/3 far (in total) from the rest yields a directed cut of ratio cost O(W)
ProvedLeightonRao.Directed.lemma_15directed-graphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1region-growingsparsest-cut
Let be a strongly connected directed network on nodes, a distance function with total weight , and with . If either
then there is a nonempty proper with
Here is the shortest directed distance from to and the shortest directed distance from to .
Formalization Note The paper states "ratio cost " and says the proof is virtually identical to Lemma 5's, whose computation (p. 800) gives from the threshold ; with the same computation gives , which is the constant stated. Strong connectivity is assumed so that the distances are the paper's (otherwise unreachable pairs would carry Lean's junk value ).
Preamble
import Mathlib import Definitions.Def_LeightonRao_Directed_Setting
Formal statement
namespace LeightonRao.Directed
/-- Leighton–Rao, Lemma 15, p. 806. If `T ⊆ V` has `|T| ≥ 2n/3` and either
`∑_{u ∈ V − T} d(T, u) ≥ 1/(4n)` or `∑_{u ∈ V − T} d(u, T) ≥ 1/(4n)`, then some directed cut has
ratio cost at most `12 W` (the constant of Lemma 5's computation, p. 800, with `1/(4n)` in place of
`1/(2n)`). -/
theorem lemma_15 {V : Type} [Fintype V] [DecidableEq V] (N : DiNetwork V)
(hn : 2 ≤ Fintype.card V) (hconn : IsStronglyConnectedNet N)
(d : V → V → ℝ) (hd : ∀ u v, 0 ≤ d u v) (T : Finset V)
(hT : 2 * (Fintype.card V : ℝ) ≤ 3 * (T.card : ℝ))
(hsum : 1 / (4 * (Fintype.card V : ℝ)) ≤ ∑ u ∈ Tᶜ, diDistFrom N d T u ∨
1 / (4 * (Fintype.card V : ℝ)) ≤ ∑ u ∈ Tᶜ, diDistTo N d u T) :
∃ U : Finset V, U.Nonempty ∧ Uᶜ.Nonempty ∧ diRatio N U ≤ 12 * diTotalWeight N d := 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, Lemma 15 (proof p. 807, referring to Lemma 5, pp. 799–800)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.