1Maximum Flow 1.1 Definitions Tarjan: Data Structures and Network Algorithms Ford 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 t Goal: assign a flow value to each edge: (raw/gross flow form) • conservation: �w g(v, w) − g(w, v) = 0 unless v = s, t • capacity: 0 ≤ g(e) ≤ u(e)(flow is feasible/legal) • Flow value |f| = �w g(s, w) − g(w, s) (in gross model). Water hose intuition. Also routing commodities, messages under bandwidth constraints, etc. Often “per unit time” flows/capacities. Maximum flow problem: find flow of maximum value. Alternative formulation: (net flow form) • Note that all that matters is difference f (v, w) − f(w, v) • Adding same in both directions has no net effect • skew symmetry: f(v, w)= −f(w, v) • conservation: �w f(v, w) = 0 unless v = s, t • capacity: f(e) ≤ u(e)(flowis feasible/legal) Equivalence: first formulation has “gross flow” g, first has “net flow” f(v, w)= g(v, w) − g(w, v). To go other way, sign of f defines “direction” of flow in g. For intuition, gross flow nice. But for analysis, we’ll focus on net flow model. Path decomposition (another picture): • claim: any s-t flow can be 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 some vertex has outflow, find a cycle and kill • corollary: flow into t equals flow out of s (global conservation) Point A. 15 minutes to here. Cuts: 1 • partition of vertices into 2 groups • s-t-cut if one has s,other t • represent as (S,S)or just S • f(S) = net flow leaving S • lemma: for any s-t cut, f (S)= |f| (all cuts carry same flow) – suppose move v from S to S. – adds f(v, S) to crossing flow value (no longer subtracting from net) – also add f(v,S) (adding to net flow value) – total change: f(v, S ∪S)= 0 Flows versus cuts: • Deduce: |f|≤u(S)= �e∈S×S u(e). • in other words, max-flow ≤ minimum s=t cut value. • soon, we’ll see equal (duality) • first, need more machinery. Residual network. • Given: flow f in graph G • define Gf to have capacities u = ue − fee • if f feasible, all capacities positive • Since fe can be negative, some residual capacities grow • Suppose f is a feasible flow in Gf • then f + f is feasible flow in G of value f + f – flow – feasible • Suppose f is feasible flow in G • then f − f is feasible flow in Gf (value |f|−|f|) • corollary:max-flows in G correspond to max-flows in Gf • Many algorithms for max-flow: – find some flow f – recurse on Gf 2How can we know a flow is maximum? • check if residual network has 0 max-flow • augmenting path: s-t path of positive capacity in Gf • if one exists, not max-flow Max-flow Min-cut • Equivalent statements: – f is max-flow – no augmenting path in Gf – |f| = u(S)for some S Proof: • if augmenting path, can increase f • let S be vertices reachable from S in Gf. All outgoing edges have f(e)= u(e) • since |f|≤u(S), equality implies maximum 1.2 Algorithms 1.2.1 Augmenting paths Can 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 then removing • diamond example (s, x), (s, y), (y, t), (x, t), (x, y). 31.2.2 max capacity augmenting path How find one? Running time: • recall flow decomposition bound • Get 1/m of flow each time. • So m log f flows suffice for integer f weakly vs. strongly polynomial bounds Works for rational capacities too. 1.3 Scaling Idea of max-capacity augment was to be greedy • get most of solution as quick as possible. • decrease residual flow quickly Another approach:scaling. Gabow ’85 . • Also [Dinitz ’73], but appeared only in Russian so, as often the case in this 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 solution big benefit: aside from scaling phase, often as simple as unit case (eg no data structures!) Basic approach: • capacities are log U bit numbers • start with all capacities 0 (max-flow easy!) • roll in one bit of capacity at a time, starting with high order and working down. • after rollin, update max-flow by finding max-flow in residual graph • effect of rollin: – double all capacities and flow values 4– double all residual capacities – add 1 to some residual capacities • after log U roll-ins, all numbers are correct, so flow is max-flow Algorithm: repeatedly • Shift in one bit at a time • Run plain augmenting paths Analysis: • before bit shift, some cut has capacity 0 • after bit shift, cut has capacity at most m • so m augmentations suffice. Running time: O(m2 log U ). Discuss relation to max capacity algorithm. polynomial, but not strongly polynomial. Point B: got here from point A 1.4 Problem Variants Multiple sinks Edge lower bounds Bipartite matching. Vertex capacities (HW). 1.5 Applications Matrix Rounding (flow with lower bounds). P rj,pmtn Cmax 1.5.1 Shortest Augmenting Path Strongly polynomial. Instead of being directly “primal” greedy, tackle a “dual” function that bounds residual. • 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 5• Consider closest to s (after change) • i has parent j on new shortest path • j didn’t get