More on Preflow Push Algorithms

Max Flows 4 Overview of today’s lecture ‹ Very quick review of Preflow Push Algorithm ‹ The Excess Scaling Algorithm z O(n2 log U) non-saturating pushes z O(nm + n2 log U) running time. ‹ A proof that Highest Preflow Push uses O(n2m1/2) non-saturating pushes. A Feasible Preflow 2 2 3 0 2 5 2 1 3 s 2 4 t 0 3 2 3 1 The excess e(j) at each node j ≠ s, t is the flow in minus the flow out. Note: total excess = flow out of s minus flow into t. Active nodes 2 2 3 0 2 5 2 1 3 s 2 4 t 0 3 2 3 1 Nodes with positive excess are called active. The preflow push algorithm will try to push flow from active nodes towards the sink, relying on d( ). Review of Distance Labels Distance labels d( ) are valid for G(x) if i. d(t) = 0 ii. d(i) ≤ d(j) + 1 for each (i,j) ∈ G(x) Defn. An arc (i,j) is admissible if rij > 0 and d(i) = d(j) + 1. Lemma. Let d( ) be a valid distance label. Then d(i) is a lower bound on the distance from i to t in the residual network. Goldberg-Tarjan Preflow Push Algorithm Procedure Preprocess begin x :=0; compute the exact distance labels d(i) for each node; xsj := usj for each arc (s,j) ∈ A(s); d(s) := n; end Algorithm PREFLOW-PUSH; begin preprocess; while there is an active node i do begin select an active node i; push/relabel(i); end; end; Preprocess Step 3 s 2 5 3 4 5 1 1 1 1 2 3 4 s 2 6 2 2 s 1 3 4 5 t 0 4 4 1 3 2 2 0t 2 3 1 3 Saturate arcs out of node s. Move excess to the adjacent arcs Relabel node s after all incident arcs have been saturated. Select, then relabel/push 3 s 2 5 3 4 5 1 1 1 1 2 3 4 s 2 6 2 2 s 1 3 4 5 t 0 4 4 1 3 2 2 0t 2 3 1 3 1 Select an active node. Push/Relabel Update excess after a push Note: Each arc gets saturated O(n) times. Select, then relabel/push 3 s 2 5 3 4 5 1 1 1 2 3 2 3 s 1 3 4 5 t 1 4 s 2 6 2 0 4 4 1 3 2 3 1 2 0t 2 2 1 Select an active node. No arc incident to the selected node is admissible. So relabel. Note. Each node gets relabeled O(n) times. Select, then relabel/push 3 s 2 5 3 4 5 1 1 1 2 3 2 3 s 1 4 5 t 1 4 s 2 6 2 0 4 4 1 3 1 2 2 3 2 1 0t 2 1 Select an active node Push/Relabel Bounding non-saturating pushes is more complex. Note that the active node became inactive. Excess Scaling Approach Let ∆ be a “scaling” parameter. In the ∆-scaling phase e(j) ≤ ∆ for all j. At the end of the scaling phase e(j) < ∆/2, for all j, at which point the ∆/2-scaling phase begins. We start with ∆ > U. The last scaling phase is the 1scaling phase. e(j) ≤ 1 for all j. At the end of the 1-scaling phase, we have a flow, and the flow is optimal. Note: the number of phases is O(log U+1) Algorithm excess scaling begin preprocess ∆ := 2⎡log U⎤; while ∆ ≥ 1 do begin while the network contains a node j with e(j) ≥ ∆/2 do begin among nodes j with e(j) ≥ ∆/2 (called large excess nodes), choose i with minimum distance label perform push/relabel(i) while ensuring that no node excess exceeds ∆; end ∆ := ∆/2 end Pushing in the 64-scaling phase s 9 j 32 ≤ e(j) ≤ 64 i e(i) < 32 “large excess” 8 7 6 62 7 5 4 6 3 9 3 2 2 s 7 1 4 55 0 t 2 8 4 0 40 5 Choose a large excess node i at minimum distance level. 25 For each admissible arc (i,j), j is not large excess. Pushing in the 64-scaling phase. 62 7 2 32 ≤ e(j) ≤ 64 i e(i) < 32 “large excess” 40 4 5 0 24 28 7 2 4 2 j Rule: push as before, except that no node excess can exceed ∆. 4 36 5 64 Push 2 units in (7,4). Then push 36 units in (7,5) Send min (e(i), rij, ∆-e(j)) units of flow in (i,j) Any non-saturating push has at least ∆/2 units of flow A new potential function s 9 Φ = Σj∈N e(j) d(j) / ∆ 8 7 6 5 4 6 3 9 3 2 2 s 7 1 4 55 0 t node 2 3 4 5 6 7 8 9 e(j) 4 0 1 0 5 35 55 40 e(j)d(j) 8 0 1 0 20 70 165 120 8 Φ = 384 / 64 = 6 The potential is the “gravitational potential” measured in units of ∆ Deposits and Relabels s Φ = Σj∈N e(j) d(j) / ∆ 9 A deposit is an operation that increases Φ. 8 7 If 9 is relabeled then 6 ∆/2 ≤ e(9) ≤ ∆. 5 4 6 3 9 3 2 2 7 s 1 4 55 0 t 8 Increasing d(9) from 3 to 4 increases Φ by at most 1. The deposits due to increasing d(9) over all iterations is at most 2n. The total deposits due to relabels is O(n2) Withdrawals and Pushes s Φ = Σj∈N e(j) d(j) / ∆ 9 A withdrawal is an operation that decreases Φ. 8 7 Pushing 2 units of flow in (7,4) decreases Φ by 2/ ∆. 6 5 e(7)d(7) decreases by 2d(7) = 4 e(4)d(4) increases by 2d(4) = 2. 4 6 3 9 3 2 2 7 s 1 4 55 0 t 8 Every push is a withdrawal. Each non-saturating push sends at least ∆/2 units of flow, and so reduces Φ by at least ½. Putting it all together Φ = Σj∈N e(j) d(j) / ∆ Deposits = increases in Φ. The total deposits over all relabels is O(n2). Withdrawals = decreases in Φ. Each push is a withdrawal. Each non-saturating push is a withdrawal of at least ½. At the beginning of a scaling phase Φ < 2n2. Conclusion: The number of non-saturating pushes is O(n2) during a scaling phase, and O(n2 log U) over all scaling phases. Running time: O(nm + n2 log U). A comment on scaling Optimality condition for preflow push: e(j) = 0 for all j. In scaling techniques, we usually have the optimality conditions getting closer and closer to being satisfied. In this case e(j) ≤ ∆ for all j during a ∆-scaling phase, and then ∆ gets reduced by a factor of 2 at each subsequent phase. Highest Level Pushing s 5 In highest level pushing, we always select an active node with the highest level. 4 3 5 2 2 3 s 1 4 5 t 0 In the example to the left, we would select node 5. Claim: if we select the active node with the highest level, the number of pushes is O(n2m1/2). Note: The proof is due to Cheriyan and Mehlhorn, and is much easier than the proof in AMO. More on highest level pushing s 9 The algorithm selects a node from level 3. Say node 9. 8 10 7 9 9 6 6 5 2 7 0 3 0 4 6 3 9 3 8 5 2 2 7 s 2 1 4 5 6 0 t 9 5 6 4 7 Case 1: the selected node can get rid of all of its flow through admissible arcs. Then the selected node becomes inactive, and another node at level 3 is selected. 7 There is at most one non-saturating push in getting rid of flow from node 9. 21 Phases s 9 A phase is a consecutive sequence of pushes all at the same level. 8 Example: we may get rid of flow from nodes 9, 8, and 5. 7 6 5 4 6 3 9 3 8 5 2 2 7 s 1 4 5 0 t Note: the maximum number of non-saturating pushes during a phase is the number of active nodes at highest level at the beginning of the phase. (e.g., 3) But: a phase can end sooner. Lemma. The number of phases is O(n2) s 9 Let d* = max (d(j) : j is active.) 8 A phase can end in two ways: 7 Way 1: when all active nodes at level d* have sent flow to level d*-1. 6 Way 2: an active node at level d* must be relabeled, and d* will increase. 5 4 6 3 9 3 8 5 2 2 7 s 1 4 5 0 t Way 2 can happen at most 2n2 times. Way 1 can happen at most n + the number of times Way 2 happens. (“d* cannot decrease more times than it increases”). Overview We want to bound the number of non-saturating pushes. Instead, we will bound the total number of non-saturating pushes per phase. Cheap phases: ones with fewer than O(m.5) nonsaturating pushes. This leads to O(n2m.5) nonsaturating pushes over all phases. Expensive phase: ones with more than O(m.5) nonsaturating pushes. We will used a potential function to bound non-saturating pushes in expensive phases. A new potential function s 9 Let d’(j) = | { i : d(i) ≤ d(j)} | 8 Example: d’(2) = | {t, 4, 2, 7} | = 4 7 d’(8) = | {t, 4, 2, 7, 9, 3, 8, 5 } | = 8 6 Φ = Σj active d’(j). 5 4 6 3 9 3 8 5 2 2 7 s 1 4 5 0 t Φ = d’(4) + d’(7) + d’(9) + d’(8) + d’(5) = 2+ 4 + 8 + 8 + 8 = 30 Deposits and relabels s 9 Φ = Σj active d’(j). 8 A deposit is an operation that increases Φ. 7 6 A relabel of 9 increases d’(9) by 1, but it decreases d’(3), d’(8) and d’(5). 5 A relabel increases Φ by less than n. 4 6 3 9 3 8 5 2 2 7 s 1 4 5 0 t The total value of all deposits from relabels is O(n3) Deposits and saturating pushes s 9 8 Φ = Σj active d’(j). A saturating push in (9,2) makes node 2 active, and increases Φ by 4. 7 6 A saturating push increases Φ by less than n. 5 4 6 3 9 3 8 5 2 2 7 s 1 4 5 0 t The total value of all deposits from saturating pushes is O(n2m) Withdrawals and non-saturating pushes s Φ = Σj active d’(j). 9 8 A withdrawal is an operation that decreases Φ. 7 The deposit from initialization is at most n2. Thus the total value of withdrawals is at most n2 plus value of deposits = O(n2m). 6 5 4 6 3 9 3 8 5 2 2 7 s 1 4 5 0 t A non-saturating push in (9,7) makes 9 inactive, and reduces Φ by 8. A non-saturating push in (9,2) makes 9 inactive, 2 active and reduces Φ by 4. Withdrawals and non-saturating pushes s 9 Φ = Σj active d’(j). Let K = m.5. In an expensive phase, there are at least K non-saturating pushes, and thus the number of nodes at level d* is at least K. 8 7 6 Each non-saturating push at an expensive phase is a withdrawal of at least K 5 4 6 3 9 3 8 5 2 2 7 s 1 4 5 0 t Note: the descendents of 9 are 9, 3, 8, 5, 2, 7, 4, t. If 9 becomes inactive, Φ decreases by 8. Node 2 has 4 fewer descendents than does node 9. If we do a non-saturating push in (9,2), Φ decreases by 4. Withdrawals and non-saturating pushes s 9 Φ = Σj active d’(j). 8 Suppose there are > K nodes at level d*. 7 Each non-saturating push decreases Φ by > K. 6 Each non-saturating push at an expensive phase is a withdrawal of at least K 5 4 6 3 9 3 8 5 2 2 7 s 1 4 5 0 t Putting it all together Φ = Σj active d’(j). Deposits = increases in Φ. The total deposits over all iterations is O(n2m) Withdrawals = decreases in Φ. Each non-saturating push during an expensive phase is for at least K. The number is O(n2m/K) Each non-saturating push during a cheap phase is for at least 1. The number non-saturating pushes during a cheap phase is at most K. The number over all phases is O(n2K). Number of non-saturating pushes is O(n2K + n2m/K) = O(n2m.5) if K = m.5. Dynamic Trees Dynamic trees is a clever data structure that permits one to send flow along a path of arcs, and it takes O(log n) steps to send the flow, regardless of the length of the path. For arcs in the dynamic tree, we keep track of residual capacities implicitly, and do not store them explicitly. We will describe dynamic trees next. Dynamic Trees Let us store all admissible current arcs in a dynamic tree called T. 2 6 5 There is at most one arc directed out of each node j, and no arc out of t. 7 8 1 9 4 t 3 Dynamic Trees We will permit several “operations” on T. 2 6 5 Each operation will take O(log n) steps if T has at most n nodes. 7 8 1 9 4 t 3 Root nodes Any node with no outgoing arcs is a root node. 2 Nodes t and 3 are root nodes. For a tree T, root(j) is the root node in the subtree containing j. Examples: root(6) = t root(7) = 3 7 6 5 1 9 4 Dynamic Tree Operation: Find-root(j) 8 t 3 Node values Each node of the tree has a value, which is the residual capacity of its outgoing arc. (The value of root nodes is ∞.) Examples. Value(4) = 5 Value(7) = 2 Value(3) = ∞ Dynamic Tree Operation: Find-value(j) 2 7 2 3 6 6 1 9 8 5 8 3 9 4 7 4 5 t Find min We want to send flow along a path. For this we need to compute the residual capacity of a path. 2 7 Find-min(j): returns the node on the path from j to root(j) with minimum value. Examples: Find-min(6) = node 9 Find-min(2) = node 2 Find-min(3) = node 3 2 3 6 Dynamic Tree Operation: 6 1 9 8 5 8 3 9 4 7 4 5 t Recall: each dynamic tree operation takes O(log n) steps. Change Value Change-value(j, val) will subtract val from every node on the path from j to root of j. Example: Change-value(6, 4) 2 7 2 3 6 6 1 9 8 4 5 8 3 9 4 0 7 4 5 1 t Cut Cut(j) deletes the arc coming out of node j, and updates the root. 2 7 2 3 6 9 8 4 5 6 1 Example: Cut(9) Examples after performing cut(9): root(2) = 9 find-min(5) = node 4 8 3 9 4 0 7 4 5 1 t Link Link(i, j, val) adds arc (i,j) to the dynamic tree with residual capacity val 2 7 8 2 3 6 6 1 Example: Link(3, 4, 7) 9 8 4 Examples after performing Link(3, 4, 7): root(8) = t find-min(1) = node 4 5 3 9 4 0 7 4 5 1 t 7 Overview of how dynamic trees are used ‹ The tree will contain current arcs, so long as the current arcs are admissible. z Delete saturated arcs from T z Delete current arcs into node j after j is relabeled z Note: each arc is deleted from T at most n times, and thus added to T at most n times. Total number of cuts and links is O(nm), and the time is O(nm log n). On Sending Flow After selecting active node j, send flow from j to its root node. 2 7 Example: if e(7) = 3 and if node 7 is selected, we can push only 1 unit to t. 2 3 6 Case 1: not all of the excess from node j is removed. 6 1 9 8 4 5 3 9 4 0 7 4 This case causes a saturation, and can happen O(nm) times. 8 5 1 t 7 On Sending Flow Case 2: all flow is sent to a root node j other than t. 2 Example: node 2 or node 6 is selected. 3 Next Step: select the root node j for a push/relabel. Either j is relabeled, or a new admissible arc from j is found. 7 2 6 6 1 9 8 4 5 3 9 4 0 7 4 5 1 Case 2 happens O(nm) times. 8 t 7 On Sending Flow Case 3: flow is sent to t and no arc is saturated. 2 Example: suppose e(3) = 2 and node 3 is selected. 3 Subsequently, the number of active nodes decreases. Case 3 can happen O(nm) times, since the number of active nodes can increase by one in cases 1 and 2, which each happen O(nm) times. 7 8 2 6 6 1 9 8 4 5 3 9 4 0 7 4 5 3 t 7 Conclusions for dynamic trees We can perform all pushes using dynamic tree operations. We store residual capacities explicitly for arcs not in the tree, but do not store them for arcs in the tree. We can carry out preflow push with O(nm) dynamic tree operations. Running time is O(nm log n). Summary of Lecture Excess scaling. By ensuring that all non-saturating pushes are at least ∆/2 and that no node has excess greater than ∆, we bound the number of nonsaturating pushes at O(n2) per scaling phase. O(nm + n2 log U) time. Highest level pushing By using a new potential function, and by carefully analyzing pushes during phases, we bound the number of non-saturating pushes at O(n2m.5). Dynamic Trees