10/15/2008 A. Smith; based on slides by S. Raskhodnikova and K. Wayne A. Smith Algorithm Design and Analysis LECTURES 22-24 Counting Simple Paths Network Flow •Maximum Fow •Minimum Cut •Ford-FulkersonReview Question How many simple paths of length k can there be in a graph with n nodes? Consider following code : Modified-DFS(u, list path-so-far): • If u is in path-so-far • return • Else • Add u to path-so-far • If size(path-so-far)<k • For all neighbors v of u • Modified-DFS(v,path-so-far) Does this run in time O(2k poly(n)) ?Network Flow and Linear Programming 10/15/2008 A. Smith; based on slides by S. Raskhodnikova and K. WayneSoviet Rail Network, 1955 Reference: On the history of the transportation and maximum flow problems. Alexander Schrijver in Math Programming, 91: 3, 2002.Maximum Flow and Minimum Cut Max flow and min cut.  Two very rich algorithmic problems.  Cornerstone problems in combinatorial optimization.  Beautiful mathematical duality. Nontrivial applications / reductions.  Data mining.  Open-pit mining.  Project selection.  Airline scheduling.  Bipartite matching.  Image segmentation.  Clustering  Network connectivity.  Network reliability.  Distributed computing.  Egalitarian stable matching.  Network intrusion detection.  Multi-camera scene reconstruction.  Data privacy.  Many many more …Flow network.  Abstraction for material flowing through the edges.  G = (V, E) = directed graph, no parallel edges.  Two distinguished nodes: s = source, t = sink.  c(e) = capacity of edge e. Minimum Cut Problem s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 capacity source sinkDef. An s-t cut is a partition (A, B) of V with s  A and t  B. Def. The capacity of a cut (A, B) is: Cuts s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 10 + 5 + 15 = 30 As 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 A Cuts Def. An s-t cut is a partition (A, B) of V with s  A and t  B. Def. The capacity of a cut (A, B) is: Capacity = 9 + 15 + 8 + 30 = 62Min s-t cut problem. Find an s-t cut of minimum capacity. Minimum Cut Problem s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 A Capacity = 10 + 8 + 10 = 28Def. An s-t flow is a function f from E to real numbers that satisfies:  For each e  E: [capacity]  For each v  V – {s, t}: [conservation] Def. The value of a flow f is: Flows 4 0 0 0 0 0 0 4 4 0 0 0 Value = 4 0 capacity flow s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 0 4Def. An s-t flow is a function f from E to real numbers that satisfies:  For each e  E: [capacity]  For each v  V – {s, t}: [conservation] Def. The value of a flow f is: Flows 10 6 6 11 1 10 3 8 8 0 0 0 11 capacity flow s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 0 Value = 24 4Max flow problem. Find s-t flow of maximum value. Maximum Flow Problem 10 9 9 14 4 10 4 8 9 1 0 0 0 14 capacity flow s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 0 Value = 28Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving s. Flows and Cuts 10 6 6 11 1 10 3 8 8 0 0 0 11 s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 0 Value = 24 4 AFlow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving s. Flows and Cuts 10 6 6 1 10 3 8 8 0 0 0 11 s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 0 Value = 6 + 0 + 8 - 1 + 11 = 24 4 11 AFlow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving s. Flows and Cuts 10 6 6 11 1 10 3 8 8 0 0 0 11 s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 0 Value = 10 - 4 + 8 - 0 + 10 = 24 4 AFlows and Cuts Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then Proof. by flow conservation, all terms except v = s are 0Question Two problems • min cut • max flow •How do they relate?Flows and Cuts Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the value of the flow is at most the capacity of the cut. Cut capacity = 30  Flow value  30 s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 Capacity = 30 A Big Optimization Idea #1: Look for structural constraints, e.g. max flow  min-cutWeak duality. Let f be any flow. Then v(f)  cap(A, B), for any s-t cut (A, B). Pf.  Flows and Cuts s t A B 7 6 8 4Certificate of Optimality Corollary. Let f be any flow, and let (A, B) be any s-t cut. If v(f) = cap(A, B), then f is a max flow and (A, B) is a min s-t cut. Value of flow = 28 Cut capacity = 28  Flow value  28 10 9 9 14 4 10 4 8 9 1 0 0 0 14 s 2 3 4 5 6 7 t 15 5 30 15 10 8 15 9 6 10 10 10 15 4 4 0 ATowards a Max Flow Algorithm Greedy algorithm.  Start with f(e) = 0 for all edge e  E.  Find an s-t path P where each edge has f(e) < c(e).  Augment flow along path P.  Repeat until you get stuck. s 1 2 t 10 10 0 0 0 0 …