Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Maximum Flow2ContentsContents.■ Maximum flow problem.■ Minimum cut problem.■ Max-flow min-cut theorem.■ Augmenting path algorithm.■ Capacity-scaling.■ Shortest augmenting path.3■ Network reliability.■ Security of statistical data.■ Distributed computing.■ Egalitarian stable matching.■ Distributed computing.■ Many many more . . .Maximum Flow and Minimum CutMax flow and min cut.■ Two very rich algorithmic problems.■ Cornerstone problem in combinatorial optimization.■ Beautiful mathematical duality.Nontrivial applications / reductions.■ Network connectivity.■ Bipartite matching.■ Data mining.■ Open-pit mining. ■ Airline scheduling.■ Image processing.■ Project selection.■ Baseball elimination.4Max flow network: G = (V, E, s, t, u) .■ (V, E) = directed graph, no parallel arcs.■ Two distinguished nodes: s = source, t = sink.■ u(e) = capacity of arc e.Max Flow NetworkCapacitys234567t1553015108159610101015445An s-t flow is a function f: E →ℜ that satisfies:■ For each e ∈ E: 0 ≤ f(e) ≤ u(e) (capacity)■ For each v ∈ V – {s, t}: (conservation)Flows∑∑=veveefef ofout to in )()(s234567t155301510815961010101544400000004404000CapacityFlow∑=∑∈ Ewvwvewvfef),(: ofout ),(:)(∑=∑∈ Evwwvevwfef),(: to in ),(:)(6An s-t flow is a function f: E →ℜ that satisfies:■ For each e ∈ E: 0 ≤ f(e) ≤ u(e) (capacity)■ For each v ∈ V – {s, t}: (conservation)MAX FLOW: find s-t flow that maximizes net flow out of the source. Flowss234567t1553015108159610101015444000000044040Value = 4∑=seeff ofout )(00CapacityFlow∑∑=veveefef ofout to in )()(7An s-t flow is a function f: E →ℜ that satisfies:■ For each e ∈ E: 0 ≤ f(e) ≤ u(e) (capacity)■ For each v ∈ V – {s, t}: (conservation)MAX FLOW: find s-t flow that maximizes net flow out of the source. Flowss234567t15530151081596101010154410661111110388040Value = 2400CapacityFlow∑∑=veveefef ofout to in )()(8An s-t flow is a function f: E →ℜ that satisfies:■ For each e ∈ E: 0 ≤ f(e) ≤ u(e) (capacity)■ For each v ∈ V – {s, t}: (conservation)MAX FLOW: find s-t flow that maximizes net flow out of the source. Flowss234567t15530151081596101010154410991414410489100Value = 2800CapacityFlow∑∑=veveefef ofout to in )()(9NetworkscommunicationNetworktelephone exchanges,computers, satellitesNodes Arcscables, fiber optics,microwave relaysFlowvoice, video,packetscircuitsgates, registers,processorswires currentmechanical joints rods, beams, springs heat, energyhydraulicreservoirs, pumpingstations, lakespipelines fluid, oilfinancial stocks, currency transactions moneytransportationairports, rail yards,street intersectionshighways, railbeds,airway routesfreight,vehicles,passengerschemical sites bonds energy10An s-t cut is a node partition (S, T) such that s ∈ S, t ∈ T.■ The capacity of an s-t cut (S, T) is:Min s-t cut: find an s-t cut of minimum capacity.Cuts∑∑∈∈∈=TwSvEwvSewvueu,),( ofout ).,(:)(s234567t155301510815961010101544Capacity = 3011An s-t cut is a node partition (S, T) such that s ∈ S, t ∈ T.■ The capacity of an s-t cut (S, T) is:Min s-t cut: find an s-t cut of minimum capacity.Cutss234567t155301510815961010101544Capacity = 62∑∑∈∈∈=TwSvEwvSewvueu,),( ofout ).,(:)(12An s-t cut is a node partition (S, T) such that s ∈ S, t ∈ T.■ The capacity of an s-t cut (S, T) is:Min s-t cut: find an s-t cut of minimum capacity.Cutss234567t155301510815961010101544Capacity = 28∑∑∈∈∈=TwSvEwvSewvueu,),( ofout ).,(:)(13L1. Let f be a flow, and let (S, T) be a cut. Then, the net flow sent across the cut is equal to the amount reaching t.Flows and Cutss234567t155301510815961010101544fefefefseSeSe==−∑∑∑ ofout to in ofout )()()(Value = 241066101001048804000141066101001048804000L1. Let f be a flow, and let (S, T) be a cut. Then, the net flow sent across the cut is equal to the amount reaching t.Flows and Cutss234567t155301510815961010101544fefefefseSeSe==−∑∑∑ ofout to in ofout )()()(Value = 2415106610100104880400L1. Let f be a flow, and let (S, T) be a cut. Then, the net flow sent across the cut is equal to the amount reaching t.Flows and Cutss234567t155301510815961010101544fefefefseSeSe==−∑∑∑ ofout to in ofout )()()(Value = 24016Let f be a flow, and let (S, T) be a cut. Then, Proof by induction on |S|.■ Base case: S = { s }.■ Inductive hypothesis: assume true for |S| < k.– consider cut (S, T) with |S| = k– S = S’ ∪ { v } for some v ≠ s, t, |S’ | = k-1 ⇒ cap(S’, T’) = | f |.– adding v to S’ increase cut capacity by Flows and Cuts.)()( to in ofout ∑∑=−Se Sefefef0)()( to in ofout =−∑∑veveefefsvtAftersvtS’BeforeS17L2. Let f be a flow, and let (S, T) be a cut. Then, | f | ≤ cap(S, T).Proof.Corollary. Let f be a flow, and let (S, T) be a cut. If |f| = cap(S, T), then f is a max flow and (S, T) is a min cut.Flows and CutsT)cap(S,)()()()( ofout ofout to in ofout =≤≤−=∑∑∑∑SeSeSeSeeuefefeffstST768418Max Flow and Min CutCorollary. Let f be a flow, and let (S, T) be a cut. If |f| = cap(S, T), then f is a max flow and (S, T) is a min cut.s234567t15530151081596101010154410991515410489100Flow value = 2800Cut capacity = 2819Max-Flow Min-Cut TheoremMAX-FLOW MIN-CUT THEOREM (Ford-Fulkerson, 1956): In any network, the value of the max flow is equal to the value of the min cut.■ "Good characterization."■ Proof IOU.s234567t15530151081596101010154410991515410489100Flow value = 2800Cut capacity = 2820Towards an AlgorithmFind an s-t path where each arc has u(e) > f(e) and "augment" flow along the path.s4253 t40000004044Flow value = 010131021Towards an AlgorithmFind an s-t path where each arc has u(e) > f(e) and "augment" flow along the path.■ Repeat until you get stuck.s4253 t40000004044Flow value = 10101310101010XXX22Towards an AlgorithmFind an s-t path where each arc has u(e) > f(e) and "augment" flow along the path.■ Repeat until you get stuck.■ Greedy algorithm fails.s4253 t10131040010101004044Flow value = 10s4253 t1013105441061045455Flow value = 1423Residual ArcsOriginal graph G = (V, E).■ Flow f(e).■ Arc e = (v, w) ∈ E.Residual graph: Gf= (V, Ef).■ Residual arcs e = (v, w) and eR= (w, v).■ "Undo" flow sent.v w176CapacityFlowv w11Residual capacity6Residual capacity24Residual