Lemma 5.1 — an active vertex admits an update
ProvedCostScaling.Refine.push_or_relabel_applicablecost-scalingminimum-cost-circulationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1push-relabel
Let a circulation network be feasible, so some circulation exists. Let be a pseudoflow that is -optimal with respect to prices , and let have positive excess. Then either a push applies to an arc for some , or a relabel applies at :
This is the progress fact used to connect the loop guard with flow conservation. Feasibility also ensures that the relabel action has an outgoing residual arc and an attained minimum, so an applicable operation is a genuine next step.
Formalization Note The formal conclusion explicitly produces a successor state for a relabel; Figure 5 says an empty relabel minimum signals infeasibility.
Preamble
import Mathlib import Definitions.Def_CostScaling_Refine_Run
Formal statement
namespace CostScaling.Refine
/-- Lemma 5.1, p. 19. Feasibility also rules out an empty relabel minimum. -/
theorem push_or_relabel_applicable {V : Type*} [Fintype V] [DecidableEq V]
(N : Network V) (ε : ℝ) (s : State V)
(hfeasible : ∃ g, CycleCanceling.MinMean.IsCirculation N g)
(hopt : IsEpsOptimal N ε s.f s.p) (v : V) (hv : IsActive N s.f v) :
(∃ w, PushApplicable N s v w) ∨ (∃ t, IsRelabelStep N ε s v t) := by sorry
end CostScaling.Refine
Source
Goldberg & Tarjan, MIT/LCS/TM-333 (July 1987), Lemma 5.1, p. 19; https://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-333.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.