1 Maximum Flow1.1 DefinitionsTarjan: Data Structures and Network AlgorithmsFord and Fulkerson, Flows in Networks, 1962 (paper 1956)Ahuja, Magnanti, Orlin Network Flows. Problem: do min-cost.Problem: in a graph, find a flow that is feasible and has maximum value.Directed graph, edge capacities u(e) or u(v, w). Why not c? reserved for costs,later.source s, sink tGoal: assign a flow value to each edge: (raw/gross flow form)• conservation:Pwg(v, w) − g(w, v) = 0 unless v = s, t• capacity: 0 ≤ g(e) ≤ u(e) (flow is feasible/legal)• Flow value |f | =Pwg(s, w) − g(w , s) (in gross model).Water hose intuition. Also routing commodities, messages under bandwidthconstraints, etc. Often “per unit time” flows/capacities.Maximum flow problem: find flow of maximum value.Path decomposition (another perspective):• claim: any s-t flow can b e decomposed into paths with quantities• proof: induction on number of edges with nonzero flow• if s has out flow, find an s-t path (why can we? conservation) and kill• if t has in-flow (won’t any more, but no need to prove) work backwardsto s and kill• if some vertex has outflow, find a cycle and kill• corollary: flow into t equals flow out of s (global conservation)• Note: every path is a flow (balanced).Point A. 15 min to here.Decision question: is there nonzero flow• Supp ose yes.• decompose into paths• proves there is a flow path• Supp ose no• then no flow path• consider vertices reachable from s1• they form a cut (s ∈ S, t ∈ T = S)• no edge crossing cutWhat about max-flow?• Need some upper bound to decide if we are maximal• Consider any flow, and cut (S, T )• decompose into paths• every path leaves the cut (at least) once• So, outgoing cut capacity must accept flow value• min cut is upper bound for max flowSupp ose have some flow. How can we send more?• Might be no path in original graph• Instead need residual graph:– Supp ose flow f (v, w)– set uf(v, w) = u(v, w) −f(v, w) (decrease in available capacity)– set uf(w, v) = u(w , v) + f(w, v) (increase in capacity indicates canremove (v, w) flow• If augmenting path in residual graph, can increase flow• What if no augmenting path?• Implies zero cut (S, T ) in residual graph• Implies every S-T edge is saturated• Implies every T -S edge is empty• i.e. cut is saturated• consider path decomposition• each path crosses the cut exactly once (cannot cross back)• so flow crossing cut equals value of flow• i.e. value of cut equals value of flow• but (again by path decomposition) value of flow cannot exceed value ofcut (because all paths cross cut)• so flow is maximum2We have proven Max-flow Min-cut duality:• Equivalent statements:– f is max-flow– no augmenting path in Gf– |f| = u(S) for some SProof:• if augmenting path, can increase f• let S b e vertices reachable from s in Gf. All outgoing e dges have f(e) =u(e) and incoming have f(e) = 0• since |f| ≤ u(S), equality implies maximumAnother cute corollary:• Net flow across any cut (in minus out) equals flow value• True for a path as it must go out once more than in• So true for a sum of pathsNote that max-flow and min-cut are witnesses to each others’ optimality.1.2 Algorithms1.2.1 Augmenting pathsCan always find one.If capacities integral, always find an integer.• So terminate• Running time O(mf)• Lemma: flow integrality• Polynomial for unit-capacity graphs• Also terminate for rationals (but not polynomial)• might not terminate for reals.Note: complex greedy algorithm• always have augmentation• but augmentations may fight each other, adding flow to an edge and thenremoving• diamond example (s, x), (s, y), (y, t), (x, t), (x, y).31.2.2 max capaci ty augmenting pathRunning time:• recall flow decomposition bound• Get 1/m of flow each time.• So m log f flows suffice for integer fHow find one? Prim.Overall, O(m2log f)weakly vs. strongly polynomial bounds• pseudopoly in magnitudes of numbers• poly (specifically weakly poly) is poly in input size including bits• strongly is poly in input size ignoring bitsWorks for rational capacities too.1.3 ScalingIdea of max-capacity augment was to be greedy• get most of solution as quick as possible.• decrease residual flow quicklyAnother approach:scaling.• Gabow ’85.• Also [Dinitz ’73], but appeared only in Russian so, as often the case inthis area, the american discovery was much later but independent.General principle for applying “unit case” to “general numeric case”.Idea: number is bits; bits are unit case!Scaling is reverse of rounding.• start with rounded down value (drop low order bits)• put back low order its, fixup solutionbig benefit: aside from scaling phase, often as simple as unit case (eg no datastructures!)Basic approach:• capacities are log U bit numbers• start with all capacities 0 (max-flow easy!)4• roll in one bit of capacity at a time, starting with high order and workingdown.• after rollin, update max-flow by finding max-flow in residual graph• effect of rollin:– double all capacities and flow values– double all residual capacities– add 1 to some residual capacities• after log U roll-ins, all numbers are correct, so flow is max-flowAlgorithm: repeatedly• Shift in one bit at a time• Run plain augmenting pathsAnalysis:• before bit shift, some cut has capacity 0• after bit shift, cut has capacity at most m• so m augmentations suffice.Running time: O(m2log U).Discuss relation to max capacity algorithm.weakly polynomialPoint B: got here from point A1.4 Problem VariantsMultiple sinksExplicit supplies/demandsEdge lower bounds• send flow along lower bounds (creating residual arcs)• creates additional demands and supplies in residual.• solve• add flow on lower bound edges to cancel imbalance of new supplies anddemandsBipartite matching.Vertex capacities (HW).51.4.1 Shortest Augmenting PathStrongly polynomial.Instead of being directly “primal” greedy, tackle a “dual” function that boundsresidual.• Idea: if s, t far apart, not much flow can fit in network• So try to push up s, t residual distance.Lemma: For shortest augment, (s.i) and (i, t) distance in residual graph non-decreasing.• Among i that got closer to s• Consider closest to s (after change)• i has parent j on new shortest path• j didn’t get closer to s• so (j, i) path got shorter• so didn’t used to have residual (j , i) edge•