Sufficiency of Gale cut conditions for real and integral flows
OpenCombOpt.Circulation.gale_conditions_imply_solution38combinatorial-optimizationgraph-algorithmsnetwork-flows
Let be a finite directed multigraph with nonnegative finite arc capacities and real node demands . Suppose the total demand is zero and every node set satisfies the incoming-cut capacity condition
\sum_{v\in V}b_v=0,\qquad \sum_{v\in A}b_v\le\sum_{e\in\delta(ar A)}u_e\quad ext{for every }A\subseteq V,where \delta(ar A) consists of arcs entering . Then there is an arc assignment with net inflow at each node and on every arc. If the capacities and demands are integral, such an assignment can be chosen integral as well. This is the sufficiency direction of Gale’s network-flow feasibility theorem.
Preamble
import Mathlib import Definitions.Def_CombOpt_Circulation_MultiDigraph import Definitions.Def_CombOpt_Circulation_delta import Definitions.Def_CombOpt_Circulation_IsIntegralVector import Definitions.Def_CombOpt_Circulation_IsSolution38 import Definitions.Def_CombOpt_Circulation_excess
Formal statement
namespace CombOpt.Circulation
variable {V E : Type*} [Fintype V] [Fintype E] [DecidableEq V]
theorem gale_conditions_imply_solution38 (G : MultiDigraph V E) (u : E → ℝ)
(hu : ∀ e, 0 ≤ u e) (b : V → ℝ)
(hcond : (∑ v, b v = 0) ∧
∀ A : Finset V, ∑ v ∈ A, b v ≤ ∑ e ∈ delta G Aᶜ, u e) :
(∃ x, IsSolution38 G u b x) ∧
(IsIntegralVector b → IsIntegralVector u →
∃ x, IsIntegralVector x ∧ IsSolution38 G u b x) := by sorry
end CombOpt.Circulation
Source
W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver, Combinatorial Optimization (Wiley, 1998), §3.3, Theorem 3.15, p. 55; sufficiency direction, including its integral form.