§7, p. 14 — an (s,t) cutset of G* has finite capacity iff I = T − {t} is an initial set
ProvedLawlerWCT.RhoMax.finite_cut_iff_initialSetLet be a digraph on a finite job set , let be real weights, and let be the network obtained by adding a source and a sink , with capacities , and on the arcs of . Let be an cutset of , i.e. a partition of the nodes of with and , and let . Then
Since is injective, this is the one-to-one correspondence between finite-capacity cutsets of and initial sets of on which the minimum-cut method for maximum-weight initial sets rests.
Formalization Note. Initial sets are closed under predecessors along directed paths (Definition 2), while the cut only sees arcs; the hypothesis that every arc of joins two jobs of makes the two notions agree. A cutset is encoded by its sink side with , ; an infinite capacity is in WithTop ℝ.
import Mathlib import Definitions.Def_LawlerWCT_RhoMax_Model
namespace LawlerWCT.RhoMax
theorem finite_cut_iff_initialSet {ι : Type*} [DecidableEq ι] (N : Finset ι)
(G : ι → ι → Prop) (hGN : ∀ i j, G i j → i ∈ N ∧ j ∈ N) (w : ι → ℝ)
(T : Finset (Node ι)) (hT : T ⊆ nodes N) (ht : Node.t ∈ T) (hs : Node.s ∉ T) :
cutCapacity N G w T < ⊤ ↔ LawlerWCT.SeriesPar.IsInitialSet G N (jobsOf N T) := by sorry
end LawlerWCT.RhoMax
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.