Theorem 12, p. 804 — for every directed uniform multicommodity flow problem, Ω(𝒮/log n) ≤ f ≤ 𝒮
ProvedLeightonRao.Directed.theorem_12There is an absolute constant such that for every directed network on nodes, the max-flow and the min-cut of its directed uniform multicommodity flow problem (demand from to for every ordered pair ) satisfy
to base . Here , where counts only the edges directed from to .
This is the directed max-flow min-cut theorem of Leighton and Rao: the directed min-cut approximates the directed uniform concurrent flow within an factor, which underlies their approximation algorithms for directed cut problems such as minimum feedback arc set.
Formalization Note The is an absolute constant, quantified before the network. The paper's standing connectivity assumption is not imposed: without strong connectivity some proper cut has capacity , so and the statement holds trivially, hence dropping it only strengthens the theorem. is required since no cut exists otherwise.
import Mathlib import Definitions.Def_LeightonRao_Directed_Setting
namespace LeightonRao.Directed
/-- Leighton–Rao, Theorem 12, p. 804. There is an absolute constant `c > 0` such that for every
directed UMFP with `n ≥ 2` nodes, `c · 𝒮 / log₂ n ≤ f ≤ 𝒮`, where `f` is the max-flow and `𝒮` the
directed min-cut. -/
theorem theorem_12 :
∃ c : ℝ, 0 < c ∧ ∀ {V : Type} [Fintype V] [DecidableEq V] (N : DiNetwork V),
2 ≤ Fintype.card V →
c * diMinCut N / Real.logb 2 (Fintype.card V) ≤ diMaxFlow N diDemand ∧
diMaxFlow N diDemand ≤ diMinCut N := by sorry
end LeightonRao.Directed
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.