A process cannot be understood by stopping it. Understanding must move with the ow of the process, must join it and ow with it.
The First Law of Mentat, in Frank Herberts Dune 6
Contrary to expectation, ow usually happens not during relaxing moments of leisure and entertainment, but rather when we are actively involved in a difcult enterprise, in a task that stretches our mental and physical abilities. . . . Flow is hard to achieve without effort. Flow is not wasting time.
Mihaly Csikszentmihalyi, Flow: The Psychology of Optimal ExperienceTheres a difference between knowing the path and walking the path.
Morpheus Laurence Fishburne, The Matrix
Maximum FlowsMinimum Cuts
In the mids, U. S. Air Force researcher Theodore E. Harris and retired U. S. Army general Frank S. Ross wrote a classified report studying the rail network that linked the Soviet Union to its satellite countries in Eastern Europe. The network was modeled as a graph withvertices, representing geographic regions, andedges, representing links between those regions in the rail network. Each edge was given a weight, representing the rate at which material could be shipped from one region to the next. Essentially by trial and error, they determined both the maximum amount of stu that could be moved from Russia into Europe, as well as the cheapest way to disrupt the network by removing links or in less abstract terms, blowing up train tracks, which they called the bottleneck. Their report, which included the drawing of the network in Figure ., was only declassified in .
I learned this story from Alexander Schrijvers fascinating survey On the history of combinatorial optimization till ; the HarrisRoss report was declassified at Schrijvers request. Ford and Fulkerson who we will meet shortly credit Harris for formulating the
. MFMC
Figure .. Harris and Rosss map of the Warsaw Pact rail network. See Image Credits at the end of the book.
This one of the first recorded applications of the maximum flow and minimum cut problems. For both problems, the input is a directed graph GV, E with two special vertices s and t, called the source and target. As in previous chapters, I will write uv to denote the directed edge from vertex u to vertex v. Intuitively, the maximum flow problem asks for the maximum rate at which some resource can be moved from s to t; the minimum cut problem asks for the minimum damage needed to separate s from t.
. Flows
An s, tflow or just a flow if the source and target vertices are clear from con text is a function f : E ! R that satisfies the following conservation constraint at every vertex v except possibly s and t:
X f uvX f vw. uw
In English, the total flow into v is equal to the total flow out of v. To keep the notation simple, we define f uv0 if there is no edge uv in the graph. The value of the flow f , denotedf , is the total net flow out of the source
vertex s:
maximumflow problem, although the precise chronology is somewhat muddled; Harris and Ross
f: X f swX f us. wu
8
thank George Dantzig for assistance in formulating the problem.
Its not hard to prove thatfis also equal to the total net flow into the target vertex t, as follows. To simplify notation, letf v denote the total net flow
out of any vertex v:
f v : X f uvX f vw.
uw
The conservation constraint implies thatf v0 or every vertex v except s
and t, so Xf v f s f t. v
On the other hPand, any flow that leaves one vertex must enter another vertex, so wemusthave vfv0.Itfollowsimmediatelythatffsft. Now suppose we have another function c: E ! R0 that assigns a non
negative capacity ce to each edge e. We say that a flow f is feasible with respect to c if 0f ece for every edge e. Most of the time we consider only flows that are feasible with respect to some fixed capacity function c. We say thataflow f saturatesedgeeif fece,andavoidsedgeeif fe0. The maximum flow problem is to compute a feasible s, tflow in a given directed graph, with a given capacity function, whose value is as large as possible.
.. Cuts
1020
s 1010 010
05 015
1010
510
515
520
t
Figure .. A feasible s, tow with value . Each edge is labeled with its owcapacity. . Cuts
An s, tcut or just cut if the source and target vertices are clear from context is a partition of the vertices into disjoint subsets S and T meaning STV and ST?where s 2 S and t 2 T .
If we have a capacity function c : E ! R0, the capacity of a cut is the sum of the capacities of the edges that start in S and end in T:
kS, Tk : X X cvw. v2S w2T
Again, if vw is not an edge in the graph, we assume cvw0. Notice that the definition is asymmetric; edges that start in T and end in S are unimportant.
. MFMC
The minimum cut problem is to compute an s, tcut whose capacity is as small as possible.
5
15
s 10 10 t
10 20
S 10 T
Figure .. An s, tcut with capacity . Each edge is labeled with its capacity.
Intuitively, the minimum cut is the cheapest way to disrupt all flow from s to t. Indeed, it is not hard to show the following relationship between flows and cuts:
Lemma .. Let f be any feasible s, tflow, and let S, T be any s, tcut. The value of f is at most the capacity of S, T. Moreover, f kS, Tk if and only if f saturates every edge from S to T and avoids every edge from T to S.
Proof: Choose your favorite flow f and your favorite cut S, T , and then follow the bouncing inequalities:
20
15
In the second step, we are just adding zeros, becausef v0 for every vertex v 2 Ss. In the fourth step, we are removing flow values f xy where
ff s
Xf v
v2S XXfvw
v2S w
XX f vw
v2S w62S
X X f vw
v2S w2T XX fvw
v2S w2T XXcvw
v2S w2T kS,Tk
XXfuv v2S u
XX f uv v2S u62S
XX f uv v2S u2T
by definition conservation constraint
math,definitionof
removing edges from S to S
definition of cut
because f uv0
because f vwcvw by definition
both x and y are in S, because they appear in both sums: positively when vx and wy, and negatively when vy and ux.
The first inequalities in this derivation is actually an equality if and only if f avoids every edge from T to S. Similarly, the second inequality is actually an equality if and only if f saturates every edge from S to T. E
This lemma immediately implies that iff kS, T k, then f must be a maximum flow, and S, Tmust be a minimum cut.
. The MaxowMincut Theorem
Surprisingly, in every flow network, there is a feasible s, tflow f and an s, t cut S, Tsuch thatf kS, T k. This is the famous MaxflowMincut Theorem, first proved by Lester Ford of shortestpath fame and Delbert Fulkerson inand independently by Peter Elias, Amiel Feinstein, and Claude Shannon of informationtheory and mazesolvingrobot fame in .
The MaxflowMincut Theorem. In every flow network with source s and target t, the value of the maximum s, tflow is equal to the capacity of the minimum s, tcut.
Ford and Fulkerson proved this theorem as follows. Fix a graph G, vertices s and t, and a capacity function c : E ! R0. The proof will be easier if we assume that G is reduced, meaning there is at most one edge between any two vertices u and v. In particular, either cuv0 or cvu0. This assumption is easy to enforce: Subdivide each edge uv in G with a new vertex x, replacing uv with a path uxv, and define cuxcxvcuv. The modified graph has the same maximum flow value and minimum cut capacity as the original graph.
.. The MaxowMincut Theorem
7
10
77
10 10
Figure .. Enforcing the onedirection assumption.
Let f be an arbitrary feasible s, tflow in G. We define a new capacity
function cf : VV ! R, call8ed the residual capacity, as follows:
:cuvf uv if uv 2 E cfuv fvu ifvu2E
0 otherwise
. MFMC
Intuitively, the residual capacity of an edge indicates how much more flow can be pushed through that edge. Because f0 and fc, these residual capacities are always nonnegative. It is possible to have cf uv0 even if uv is not an edge in the original graph G. Thus, we define the residual graph GfV, Ef , whereEf isthesetofedgeswhoseresidualcapacityispositive.Mostresidual graphs are not reduced; in particular, if 0f uvcuv, then the residual graphGf containsbothuvanditsreversalvu.
05 5
1020 515
10 5
10 15 10 s1010 510ts1055t
015
010 520 1010
10
5
15
Figure .. A ow f in a weighted graph G and the corresponding residual graph Gf .
Now we have two cases to consider: Either there is a directed path from the
source vertex s to the target vertex t in the residual graph G f , or there isnt.
FirstsupposetheresidualgraphGf containsadirectedpathPfromstot;we call P an augmenting path. Let Fminuv2P cf uv denote the maximum amount of flow that we can push through P. We define a new flow f 0 : E ! R in the original graph as follows:
0 8: f uvF if uv 2 P f uv fuvF ifvu2P
5
10 5
f uv otherwise 1020
55
10
s 10 10
55
10 15
10 5
t
s 510 510
015
1010
515
010 t 1020
15
Figure .6. An augmenting path with value F5 and the resulting augmented ow f 0.
I claim that this new flow f 0 is feasible with respect to the original capacities c, meaning f 00 and f 0c everywhere. Consider an edge uv in the original graph G. There are three cases to consider.
If the augmenting path P contains uv, then
f0uvfuvFfuv0
10
because f is feasible, and
f0uv fuvF
f uvcf uv
f uvcuvf uvcuv
bydefinitionof f0 by definition of F by definition of cf
Duh.
If the augmenting path P contains the reversed edge vu, then f0uvfuvFfuvcuv,
again because f is feasible, and
f0uv fuvF bydefinitionof f0f uvcf vu by definition of Ff uvf uv by definition of cf 0 Duh.
Finally, if neither uv nor vu is in the augmenting path, then f 0uvf uv, and therefore 0f 0uvcuv, because f is feasible.
So f is indeed feasible.
Finally, only the first edge in the augmenting path leaves s, which implies
f 0f Ff . Thus, f 0 is a feasible flow with larger value than f . We conclude that if there is a path from s to t in the residual graph Gf , then f is not a maximum flow.
Ontheotherhand,supposetheresidualgraphGf doesnotcontainadirected path from s to t. Let S be the set of vertices that are reachable from s in Gf , and let TVS. The partition S, T is clearly an s, tcut. For every vertex u 2 S and v 2 T , we have
cfuvcuvfuvfvu0.
The feasibility of f implies cuvf uv0 and f vu0, so in fact we must have cuvf uv0 and f vu0. In other words, our flow f saturates every edge from S to T and avoids every edge from T to S. Lemma . now implies that f kS, Tk, which means f is a maximum flow and S, T is a minimum cut.
This completes the proof! E
.. The MaxowMincut Theorem
. MFMC
. Ford and Fulkersons augmentingpath algorithm
Ford and Fulkersons proof of the MaxflowMincut Theorem immediately sug gests an algorithm to compute maximum flows: Starting with the zero flow, repeatedly augment the flow along any path from s to t in the residual graph, until there is no such path.
This algorithm has an important but straightforward corollary:
Integrality Theorem. If all capacities in a flow network are integers, then there is a maximum flow such that the flow through every edge is an integer.
Proof: We argue by induction that after each iteration of the augmenting path algorithm, all flow values and all residual capacities are integers.
Before the first iteration, all flow values are 0 which is an integer, and all residual capacities are the original capacities, which are integers by definition.
In each later iteration, the induction hypothesis implies that the capacity F of the augmenting path is an integer, so augmenting changes the flow on each edge, and therefore the residual capacity of each edge, by an integer.
In particular, each iteration of the augmenting path algorithm increases the value of the flow by a positive integer. It follows that the algorithm eventually halts and returns a maximum flow. E
If every edge capacity is an integer, then conservatively, the FordFulkerson algorithm halts after at most fiterations, where fis the actual maximum flow. In each iteration, we can build the residual graph Gf and perform a whateverfirstsearch to find an augmenting path in OE time. Thus, in this setting, the algorithm runs in OE ftime in the worst case.
Jack Edmonds and Richard Karp observed that this running time analysis is essentially tight. Consider the node network in Figure ., where X is some large integer. The maximum flow in this network is clearly 2X. However, FordFulkerson might alternate between pushing one unit of flow along the augmenting path suvt and then pushing one unit of flow along the augmenting path svut, leading to a running time of Xf .
v
XX s1t
XX
u
Figure .. Edmonds and Karps bad example for the FordFulkerson algorithm.
.. Ford and Fulkersons augmentingpath algorithm
Ford and Fulkersons algorithm is usually fast in practice, and it is always fast when the maximum flow value fis small, but without further constraints on the augmenting paths, this is not an ecient algorithm in worst case. Edmonds and Karps bad example network can be described using only Olog Xbits; thus, the running time of FordFulkerson is actually exponential in the input size.
TMIrrational Capacities
But what if the capacities are not integers? If we multiply all the capacities by the same positive constant, the maximum flow increases everywhere by the same constant factor. It follows that if all the edge capacities are rational, then the FordFulkerson algorithm eventually halts, although still in exponential time in the number of bits used to described the input.
However, if we allow irrational capacities, the algorithm can actually loop forever, always finding smaller and smaller augmenting paths. Worse yet, this infinite sequence of augmentations may not even converge to the maximum flow, or even to a significant fraction of the maximum flow! The smallest network that exhibits this bad behavior was discovered by Uri Zwick in .
Consider the sixnode network shown in Figure .. Six of the nine edges have some large integer capacity X, two have capacity 1, and one has capacity p5120.618034, chosen so that 12. To prove that the FordFulkerson algorithm can get stuck, we can watch the residual capacities of the three horizontal edges as the algorithm progresses. The residual capacities of the other six edges will always be at least X3.
s
XXX 11
XXX
t
ABC
Figure .8. Uri Zwicks nonterminating ow example, and three augmenting paths. Suppose the FordFulkerson algorithm starts by choosing the central aug
menting path, shown at the top of Figure .. The three horizontal edges, in
In , Ford and Fulkerson described a more complex network, withvertices andedges, with the same bad behavior.
. MFMC
order from left to right, now have residual capacities 1, 0, and . Suppose inductively that the horizontal residual capacities are k1, 0, and k for some nonnegative integer k.
. Augment along path B, adding k to the flow; the residual capacities are now k1, k, and 0.
. Augment along path C, adding k to the flow; the residual capacities are now k1, 0, and k.
. Augment along path B, adding k1 to the flow; the residual capacities are now 0, k1, and k2.
. Augment along path A, adding k1 to the flow; the residual capacities are now k1, 0, and k2.
It follows by induction that after 4n1 augmentation steps, the horizontal edges have residual capacities 2n2, 0, and 2n1. As the number of augmentations grows to infinity, the value of the flow converges to
12X1 i 1 2 4p57, i1 1
even though the maximum flow value is clearly 2X17.
Practicallyminded readers might wonder why anyone should care about irrational capacities; after all, computers cant represent anything but small integers or small dyadic rationals exactly. Good question! The mathematicians answer is that the restriction to integer capacities is literally artificial; its an artifact of digital computational hardware or perhaps the otherwise irrelevant laws of physics, not an inherent feature of the abstract computational problem. But a more practical reason is that the behavior of the algorithm with irrational inputs tells us something about its worstcase behavior in practice with floating point capacitiesterrible! Even with very reasonable capacities, a careless implementation of FordFulkerson could enter an infinite loop, simply because of roundo error, without ever coming close to the correct answer.
. Combining and Decomposing Flows
Flows are normally defined as functions on the edges of a graph satisfying certain constraints at the vertices. However, flows have a second characterization that is more natural and useful in certain contexts.
Consider an arbitrary graph G with source vertex s and target vertex t. Fix any two s, tflows f and g and any two real numbersand , and consider the function h: E ! R defined by setting
6
huv : f uvguv
foreveryedgeuv;wecanwritethisdefinitionmoresimplyashf g. Straightforward definitionchasing implies that h is also an s, tflow with value hf g. More generally, any linear combination of s, tflows is also an s, tflow.
It turns out that any s, tflow can be written as a weighted sum of flows with a special structure. For any directed path P from s to t, we define a corresponding path flow as follows:
setting
8:1 if uv 2 C,
81 Puv:1
0
if uv 2 P, if vu 2 P, otherwise.
Straightforward definitionchasing implies that the function P : E ! R is indeed an s, tflow with value 1. I am deliberately overloading the variable P to mean both the path a sequence of vertices and directed edges and the unit flow along that path.
Similarly, for any directed cycle C, we define a corresponding cycle flow by
Cuv1
0 otherwise.
Again, it is easy to verify that C : E ! R is an s, tflow with value zero.
Our earlier argument implies that any linear combination of path flows and cycle flows is another flow; this weighted sum is called a flow decomposition. Moreover, every nonnegative flow has a flow decomposition with the following
special structure.
Flow Decomposition Theorem. Every nonnegative s, tflow f can be writ ten as a positive linear combination of directed s, tpaths and directed cycles. Moreover, a directed edge uv appears in at least one of these paths or cycles if and only if f uv0, and the total number of paths and cycles is at most the number of edges in the network.
Proof: We prove the theorem by induction on the number of edges carrying nonzero flow, intuitively by running the FordFulkerson algorithm backward. As long as at least one edge in the graph carries positive flow, we can find either an s, tpath or a directed cycle that carries flow. Subtracting as much flow as possible from that path or cycle empties at least one edge, so the Recursion Fairy can give us the rest of the decomposition.
To formalize this argument, we first consider the special case of circulations; these are flows with value 0, where flow is conserved at every vertex. Fix an
if vu 2 C,
.. Combining and Decomposing Flows
. MFMC
4
94 3
s53t 6 11
4 445
14 15
53 566
3
8
563 456
Figure .. Decomposing a circulation into weighted directed cycles.
arbitrary circulation f in an arbitrary flow network, and let f denote the number of edges uv such that f uv0. We prove that f can be decomposed into a positive linear combination of at most max0,f1 cycles, by induction onf . There are three cases to consider:
Iff0, then f is vacuously a linear combination of zero cycles.
Suppose f uv0 for a single directed cycle of edges uv. Then f2,
and f is trivially a linear combination of one cycle.
Otherwise, pick an arbitrary edge uv with f uv0. Consider an arbi trary walk v0v1v2 with v0u and v1v, such that f vi1vi0 for every index i. The conservation constraint implies that every vertex with incoming flow also has outgoing flow, so we can make this walk arbitrarily long; in particular, the walk must eventually visit some vertex more than once. Let k be the smallest index such that vjvk for some index jk. The subwalk vjvj1vk is a simple directed cycle C.
DefineF:mine2C fe,andconsiderthefunctionf0:fFC,or
more verbosely,
f0uv:fuvF ifuv2C,
f uv otherwise.
Straightforward definitionchasing shows that f 0 is another feasible circu lation in G. There is at least one edge e 2 C such that feF, and therefore f 0e0, which impliesf 0 f1. Since fewer edges carry flow in f 0 than in f , the Recursion Fairy can decompose f 0 into at mostf 01 f2 cycles. Adding F units of flow around cycle C gives us a flow decomposition for f ; more succinctly: ff 0FC.
Now let f be an arbitrary s, tflow in an arbitrary flow network, such that f 0. Add an edge ts to the network, and define a circulation f 0 by setting f 0tsfand f 0uvf uv for every original edge uv; observe that f 0f12. The previous argument implies that the circulation f 0 is a positive linear combination of at mostf 01 directed cycles. Deleting the edge ts gives us a decomposition of the original flow f into at most f 01f paths and cycles. Specifically, cycles in f 0 that include ts become s, tpaths in f , and cycles in f 0 that do not include ts remain cycles in f . E
The proof of the Flow Decomposition Theorem implies stronger results in two interesting special cases.
Any circulation can be decomposed into a weighted sum of cycles; no paths are necessary.
Anyacyclics,tflowcanbedecomposedintoaweightedsumofs,tpaths; no cycles are necessary.
Moreover, by canceling flow cycles until no more remain, we can transform any flow into an acyclic flow with the same value. In particular, every flow network supports a maximum s, tflow that is acyclic.
The proof also immediately translates directly into an algorithm, similar to FordFulkerson, to decompose any s, tflow into paths and cycles. The algorithm repeatedly seeks either a directed s, tpath or a directed cycle in the remaining flow, and then subtracts as much flow as possible along that path or cycle, until the flow is empty. We can find a flow path or cycle in OV time as follows:
If any edge leaving s has positive flow, follow an arbitrary walk from s in the flow graph until it either reaches t giving us a flow path or reaches some vertex for the second time giving us a flow cycle.
If no edge leaving s has positive flow, find any other vertex v with positive outflow, and follow an arbitrary walk from v in the flow graph until it reaches some vertex for the second time giving us a flow cycle.
In both cases, the conservation constraint implies that this algorithm will never get stuck. Each iteration takes OVtime and removes at least one edge from the flow graph; thus, the entire decomposition algorithm runs in OVE time.
Flow decompositions provide a natural lower bound on the running time of any maximumflow algorithm that builds the flow one path or cycle at a time. Every flow can be decomposed into at most E paths and cycles, each of which uses at most V edges, so the overall complexity of the flow decomposition is OV E. Moreover, it is easy to construct flows for which every flow decomposition has complexity VE. Thus, any maximumflow algorithm that explicitly constructs a flow one path or cycle at a timein particular, any implementation
.. Combining and Decomposing Flows
. MFMC
of Ford and Fulkersons augmenting path algorithmmust take V E time in the worst case.
.6 Edmonds and Karps Algorithms
Ford and Fulkersons algorithm does not specify which path in the residual graph to augment; the poor worstcase behavior of the algorithm can be blamed on poor choices for the augmenting path. In the early s, Jack Edmonds and Richard Karp published two natural rules for choosing augmenting paths, both of which led to more ecient algorithms.
Fattest Augmenting Paths
Edmonds and Karps first rule is essentially a greedy algorithm:
Its not hard to show that the maximumbottleneck s, tpath in a directed graph can be computed in OE log Vtime using a bestfirst traversal, similar to Jarniks minimumspanningtree algorithm or Dijkstras shortestpath algorithm. The algorithm grows a directed tree T, rooted at s, one vertex at a time, by repeatedly adding the highestcapacity edge leaving T to T, until T contains a path from s to t. Alternately, one could emulate Kruskals algorithminsert edges one at a time in decreasing capacity order until there is a path from s to talthough this approach is less ecient, at least when the graph is directed.
To complete the runningtime analysis of the flow algorithm, we need an upper bound on the number of iterations before the algorithm halts. In fact, for arbitrary real capacities, the algorithm may never halt; see Exercise . For integer capacities, however, we can bound the number of iterations as a function of the maximum flow value f , as follows.
Let f be any flow in G, and let f0 be the maximum flow in the current residual graph Gf . At the beginning of the algorithm, GfG and f 0f . We have already proved that f 0 can be decomposed into at most E paths and cycles. A simple averaging argument implies that at least one of the paths in this decomposition must carry at least f 0E units of0flow. It follows immediately that the fattest s, tpath in Gf carries at least f E units of flow.
Thus, augmenting f along the maximumbottleneck path in Gf multiplies thevalueoftheremainingmaximumflowinGf byafactorofatmost11E. In other words, the residual maximum flow value decays exponentially with the number of iterations. After Eln f iterations, the maximum flow value in G f
isatmostElnflnf
f 11E f e 1.
Choose the augmenting path with largest bottleneck value.
ThatsEulersconstante,nottheedgee. Sorry. Inparticular,afterElnf iterations, the residual maximum flow value is less than 1. If all capacities are integers, the residual maximum flow value is also an integer, so it must be 0; in other words, f is a maximum flow!
We conclude that for graphs with integer capacities, the EdmondsKarp fattest path algorithm runs in OE2 log E log ftime. Unlike the worstcase running time of raw FordFulkerson, this time bound is actually a polynomial
function of the input size.
Just like the original FordFulkerson algorithm, the fattest path algorithm
can get stuck in an infinite loop in networks with arbitrary real capacities. However, our analysis implies that even if the algorithm never halts, it maintains a flow f that approaches a maximum flow in the limit.
Shortest Augmenting Paths
The second EdmondsKarp rule was actually proposed as a practical heuristic by Ford and Fulkerson in their original maximumflow paper; a variant of this rule was independently proposed inby the Russian mathematician Yefim Dinitz.
The shortest augmenting path can be found in OE time by running breadthfirst search in the residual graph. Surprisingly, the resulting algorithm halts after a polynomial number of iterations, independent of the actual edge capacities!
The proof of this polynomial upper bound relies on two observations about the evolution of the residual graph. Let fi be the current flow after i augmentation steps, let Gi be the corresponding residual graph. In particular, f0 is zero everywhere and G0G. For each vertex v, let leveliv denote the unweighted shortestpath distance from s to v in Gi, or equivalently, the level of v in a breadthfirst search tree of Gi rooted at s. In particular, if there is no path from s to v in Gi, then leveliv1 because min?1.
Our first observation is that the level of a vertex can only increase over time.
Lemma .. levelivleveli1v for all vertices v and all integers i0.
Proof: Fix an arbitrary positive integer i0 and an arbitrary vertex v. We prove the claim by induction on leveliv and not on the integer i. As an inductive hypothesis, assume for every vertex u such that leveliuleveliv, that leveliuleveli1u. There are three cases to consider.
Specifically, Dinitz discovered a more complex maximumflow algorithm, while he was a student in an algorithms class taught by Georgy AdelsonVelsky the AV in AVL trees, in response to an inclass exercise. Dinitzs algorithm also pushes flows along shortest paths, but with additional bookkeeping to reduce the running time from OVE2 to OV2E.
.6. Edmonds and Karps Algorithms
Choose the augmenting path with the smallest number of edges.
. MFMC
If vs, we immediately have levelisleveli1s0.
If there is no path from s to v in Gi, then leveliv1leveli1v.
Otherwise, let suv be any unweighted shortest path from s to v in the graph Gi. Because this is a shortest path, we have levelivleveliu1, so the inductive hypothesis implies leveliuleveli1u. To complete the proof, we need to show that leveli1uleveli1v1. We have two subcases to consider.
If uv is an edge in Gi1, then leveli1vleveli1u1, because the levels are defined by breadthfirst traversal.
On the other hand, if uv is not an edge in Gi1, then its reversal vu must be an edge in the ith augmenting path, which by definition is the shortest path from s to t in Gi1. It follows that leveli1vleveli1u1leveli1u1.
Inbothsubcases,weconcludethatlevelivleveliu1leveli1u1 leveli1v. E
Whenever we augment the flow, the bottleneck edge in the augmenting path disappears from the residual graph, and some edges in the reversal of the augmenting path may reappear. Our second observation is that an edge cannot appear or disappear too many times.
Lemma .. During the execution of the EdmondsKarp shortestaugmenting pathalgorithm,eachedgeuvdisappearsfromtheresidualgraphGf atmost V 2 times.
Proof: Suppose uv is in two residual graphs Gi and Gj1, but not in any of the intermediate residual graphs Gi1,,Gj, for some ij. Then uv must be in the ith augmenting path, so leveli vleveli u1, and vu must be on the jth augmenting path, so leveljvlevelju1. The previous lemma implies that
leveljuleveljv1leveliv1leveliu2.
In other words, between the disappearance and reappearance of uv, the distance from s to u increased by at least 2. Because every level is either less than V or infinite, the number of disappearances is at most V 2. E
Now we can derive an upper bound on the number of iterations. Because each edge disappears at most V 2 times, there are at most E V 2 edge disappearances overall. But at least one edge disappears on each iteration, so the algorithm must halt after at most EV2 iterations. Finally, each iteration requires OE time, so the overall algorithm runs in OVE2 time.
Technique
Blocking ow Network simplex
Pushrelabel generic Pushrelabel FIFO Pushrelabel highest label Pushrelabeladd games
Pseudoow
Pseudoow highest label Incremental BFS
The fastest known purely combinatorial maximumflow algorithm, an nounced by James Orlin in , runs in OVE time, exactly matching the worstcase complexity of a flow decomposition. The details of Orlins algorithm are far beyond the scope of this book; in addition to his own new techniques, Orlin uses several older algorithms and data structures as black boxes, most of which are themselves quite complicated. In particular, Orlins algorithm does not construct an explicit flow decomposition; in fact, for graphs with only OVedges, an extension of his algorithm actually runs in only OV 2 log Vtime! Nevertheless, for purposes of analyzing algorithms that use maximum flows,
To keep this table short, I have deliberately omitted algorithms whose running time depends on edge capacities or the maximum flow value. Even with this restriction, the list is embarrassingly incomplete!
Direct With dynamic trees
OV2E OVElogV OV2E OVElogV
OV2E
OV3 OVElogV2E OV2pE
OVElogEVlogVV
OV2E OVElogV OV3 OVElogV2E OV2E OVElogV2E
OVE
Figure .. Several purely combinatorial maximumow algorithms and their running times.
Sources
Dinitz; Karzanov; Even and Itai; Sleator and Tarjan
Dantzig; Goldfarb and Hao; Goldberg, Grigoriadis, and Tarjan
Goldberg and Tarjan
Goldberg and Tarjan
Cheriyan and Maheshwari; Tuncel
Cheriyan and Hagerup; King, Rao, and Tarjan
Hochbaum
Hochbaum and Orlin
Goldberg, Held, Kaplan, Tarjan, and Werneck
.. Further Progress
. Further Progress
This is nowhere near the end of the story for maximumflow algorithms. Decades of further research have led to several faster algorithms, some of which are summarized in Figure .. All the listed algorithms listed compute a maximum flow in several iterations. Most of these algorithms have two variants: a simpler version that performs each iteration by brute force, and a faster variant that uses sophisticated data structures to maintain a spanning tree of the flow network, so that each iteration can be performed and the spanning tree updated in logarithmic time. There is no reason to believe that the best algorithms known so far are optimal; indeed, maximum flows are still a very active area of research.
Compact networks
Orlin
. MFMC
If cuvcvu, change the capacity of uv to cuvcvu and delete vu.
this is the time bound you should cite. So write the following sentence on your cheat sheets and cite it in your homeworks:
Finally, faster maximumflow algorithms are known for unitcapacity net works, where every edge has capacity 1. In , Alexander Karzanov proved that Dinitzs blockingflow algorithmthe first algorithm listed in the table aboveruns in OminV 23, E12 E time in this setting. This time bound appears to break the V E flow decomposition barrier, but in fact Karzanovs analysis implies that any flow in a unitcapacity network can be decomposed into paths with total complexity OminV 23, E12 E. This was the fastest algorithm known in this setting for four decades. Karzanovs record was finally broken in , when Aleksander Mdry announced a truly remarkable algorithm that computes maximum flows in unitcapacity networks in OE107 polylog E time. Again, the details of Mdrys algorithm are far beyond the scope of this book, or indeed the expertise of its author.
Exercises
. Suppose you are given a directed graph GV, E, two vertices s and t, a capacity function c : E ! R, and a second function f : E ! R. Describe an algorithm to determine whether f is a maximum s, tflow in G.
. Let f and f 0 be two feasible s, tflows in a flow network G, such that f0f. Provethatthereisafeasibles,tflowwithvaluef0finthe residual network Gf .
. Let uv be an arbitrary edge in an arbitrary flow network G. Prove that if there is a minimum s, tcut S, T such that u 2 S and v 2 T, then there is nominimumcutS0,T0suchthatu2T0 andv2S0.
. Let S, T and S0, T0 be minimum s, tcuts in some flow network G. Prove that SS0, TT0 and SS0, TT0 are also minimum s, tcuts in G.
. Let G be a flow network that contains an opposing pair of edges uv and vu, both with positive capacity. Let G0 be the flow network obtained from G by decreasing the capacities of both of these edges by mincuv, cvu. In other words:
Maximum flows can be computed in OVE time.
If cuvcvu, change the capacity of vu to cvucuv
and delete uv.
Finally, if cuvcvu, delete both uv and vu.
7
10 5
5
Figure .. Enforcing the onedirection assumption.
Prove that every maximum s, tflow in G0 is also a maximum s, tflow in G. Thus, by simplifying every opposing pair of edges in G, we obtain a new reduced flow network with the same maximum flow value as G.
Prove that every minimum s, tcut in G is also a minimum s, tcut in G0 and vice versa.
Prove that there is at least one maximum s, tflow in G that is not a maximum s, tflow in G0.
Describe an ecient algorithm to determine whether a given flow network contains a unique maximum s, tflow.
Describe an ecient algorithm to determine whether a given flow network contains a unique minimum s, tcut.
Describe a flow network that contains a unique maximum s, tflow but does not contain a unique minimum s, tcut.
Describe a flow network that contains a unique minimum s, tcut but does not contain a unique maximum s, tflow.
Exercises
3
a
b c
. a b c d
. An s, tflow in a network G is acyclic if there are no directed cycles where every edge has a positive flow value; that is, the subgraph of edges with positive flow value is a dag.
a Describe and analyze an algorithm to compute an acyclic maximum s, tflow in a given flow network. Your algorithm should have the same asymptotic running time as FordFulkerson.
b Describeandanalyzeanalgorithmtodeterminewhethereverymaximum s, tflow in a given flow network is acyclic.
. Let GV, E be a flow network in which every edge has capacity 1 and the shortestpath distance from s to t is at least d.
. MFMC
6
a Prove that the value of the maximum s, tflow is at most Ed.
b Now suppose that G is simple, meaning that for all vertices u and v, there is at most one edge from u to v. Flow networks can have parallel edges. Prove that the value of the maximum s,tflow is at most OV2d2. Hint: How many nodes are in the average level of a BFS tree rooted at s?
. Suppose we are given a flow network GV, E in which every edge has capacity 1, together with an integer k. Describe and analyze an algorithm to identify k edges in G such that after deleting those k edges, the value of the maximum s, tflow in the remaining graph is as small as possible.
. The analysis in our proof of the Flow Decomposition Theorem can be tightened. Let GV, E be an arbitrary flow network, and let f be an arbitrary s, tflow in G.
a Provethatiff0,then f istheweightedsumofatmostEV1 directed cycles, where f e0 for every edge e in each of these cycles.
b Provethatiff0,then f istheweightedsumofatmostEV2 directed paths and directed cycles, where f e0 for every edge e in each of these paths and cycles.
c Prove that both of the previous upper bounds are tight: There are graphs in which some circulations cannot be decomposed into less than EV1 cycles, and some flows cannot be decomposed into less than EV2 paths and cycles. Hint: This is easy.
. Our observation that any linear combination of s, tflows is itself an s, t flow implies that the set of all not necessarily feasible s, tflows in any graph actually define a real vector space, which we can call the flow space of the graph.
a Prove that the flow space of any connected graph GV, E has dimen sion EV2.
b Let T be any spanning tree of G. Prove that the following collection of paths and cycles define a basis for the flow space:
TheuniquepathinTfromstot;
The unique cycle in Te, for every edge e 62 T.
c Let T be any spanning tree of G, and let F be the forest obtained by deleting any single edge in T. Prove that the following collection of paths and cycles define a basis for the flow space:
TheuniquepathinFefromstot,foreveryedgee62Fthathas one endpoint in each component of F;
The unique cycle in Fe, for every edge e 62 F with both endpoints in the same component of F.
d Prove or disprove the following claim: Every connected flow network has a flow basis that consists entirely of simple paths from s to t.
. Cuts are sometimes defined as subsets of the edges of the graph, instead of as partitions of its vertices. In this problem, you will prove that these two definitions are almost equivalent.
We say that a subset X of directed edges separates s and t if every directed path from s to t contains at least one directed edge in X . For any subset S of vertices, let S denote the set of directed edges leaving S; that is, S : uvu 2 S, v 62 S.
a Prove that if S, T is an s, tcut, then S separates s and t.
b Let X be an arbitrary subset of edges that separates s and t. Prove that
there is an s,tcut S,T such that SX.
c Let X be a minimal subset of edges that separates s and t. Such a set of edges is sometimes called a bond. Prove that there is an s, tcut S,T such that SX.
. Suppose instead of capacities, we consider networks where each edge uv has a nonnegative demand duv. Now an s, tflow f is feasible if and only if f uvduv for every edge uv. Feasible flow values can now be arbitrarily large. A natural problem in this setting is to find a feasible s, tflow of minimum value.
a Describe an ecient algorithm to compute a feasible s, tflow, given the graph, the demand function, and the vertices s and t as input. Hint: Find a flow that is nonzero everywhere, and then scale it up to make it feasible.
b Suppose you have access to a subroutine MF that computes maximum flows in networks with edge capacities. Describe an ecient algorithm to compute a minimum flow in a given network with edge demands; your algorithm should call MF exactly once.
c State and prove an analogue of the maxflow mincut theorem for this setting. Do minimum flows correspond to maximum cuts?
. ForanyflownetworkGandanyverticesuandv,letbottleneckGu,vdenote the maximum, over all pathsin G from u to v, of the minimumcapacity edge along .
Exercises
. MFMC
8
a Describe and analyze an algorithm to compute bottleneckGs,t in OElogV time. This is the amount of flow that the EdmondsKarp fattestaugmentingpaths algorithm pushes in the first iteration.
b Now suppose the flow network G is undirected; equivalently, suppose cuvcvu for every pair of vertices u and v. Describe and analyze an algorithm to compute bottleneckGs, t in OVE time. Hint: Find the median edge capacity. Why doesnt this speedup work for directed graphs?
TMc Again, suppose the flow network G is undirected. Describe and an alyze an algorithm to construct a spanning tree T of G such that bottleneckT u, vbottleneckG u, v for all vertices u and v. Edges in T inherit their capacities from G. For full credit, your algorithm should run in OE time.
. Suppose you are given a flow network G with integer edge capacities and an integer maximum flow fin G. Describe algorithms for the following operations:
a Ie: Increase the capacity of edge e by 1 and update the maximum flow.
b De: Decrease the capacity of edge e by 1 and update the maximum flow.
Both algorithms should modify fso that it is still a maximum flow, more quickly than recomputing a maximum flow from scratch.
. Let G be a network with integer edge capacities. An edge in G is upper binding if increasing its capacity by 1 also increases the value of the maximum flow in G. Similarly, an edge is lowerbinding if decreasing its capacity by 1 also decreases the value of the maximum flow in G.
a Does every network G have at least one upperbinding edge? Prove your answer is correct.
b Does every network G have at least one lowerbinding edge? Prove your answer is correct.
c Describe an algorithm to find all upperbinding edges in G, given both G and a maximum flow in G as input, in OE time.
d Describe an algorithm to find all lowerbinding edges in G, given both G and a maximum flow in G as input, in OEV time.
. A given flow network G may have more than one minimum s, tcut. Lets define the best minimum s, tcut to be any minimum cut S, T with the smallest number of edges crossing from S to T .
a Describe an ecient algorithm to find the best minimum s, tcut when the capacities are integers.
b Describe an ecient algorithm to find the best minimum s, tcut for arbitrary edge capacities.
c Describe an ecient algorithm to determine whether a given flow network contains a unique best minimum s, tcut.
. Anewassistantprofessor,teachingmaximumflowsforthefirsttime,suggests the following greedy modification to the generic FordFulkerson augmenting path algorithm. Instead of maintaining a residual graph, just reduce the capacity of edges along the augmenting path! In particular, whenever we saturate an edge, just remove it from the graph. Who needs all that residual graph nonsense?
a Show that GF does not always compute a maximum flow.
b Show that GF is not even guaranteed to compute a good approximation to the maximum flow. That is, for any constant 1, there is a flow network G such that the value of the maximum flow is more thantimes the value of the flow computed by GF. Hint: Assume that GF chooses the worst possible pathat each iteration.
. InMaurice Queyranne published an example of a flow network, shown below, where Edmonds and Karps fattest path heuristic does not halt. As in Zwicks bad example for the original FordFulkerson algorithm,denotes the inverse golden ratio p512. The three vertical edges play essentially the same role as the horizontal edges in Zwicks example.
The adverb just is almost always subconscious shorthand for Im too lazy to figure out the details, but you should believe me anyway, or more succinctly, This is probably wrong. See also merely, simply, clearly, and obviously.
Exercises
GFG,c,s,t: for every edge e in G
fe 0
while there is a path from s to t
an arbitrary path from s to t
F minimum capacity of any edge infor every edge e in
f e f eF if ceF
remove e from G
else
ce ceF return f
. MFMC
s 12 a 12 b 2 c 12 d 2 12212 1 12 12
e 2 f 12 g 12 h 2 t
Figure .. Queyrannes network, and a sequence of fattest path augmentations.
a Show that the following infinite sequence of path augmentations is a valid execution of the EdmondsKarp fattest path algorithm. See the bottom of Figure ..
QFP:
for i 1 to 1
push 3i2 units of flow along saf gbhcdt push 3i1 units of flow along sf abghct push 3i units of flow along sef agbcht
b Describe a sequence of O1 path augmentations that yields a maximum flow in Queyrannes network.
TM. An s, tseriesparallel graph is a directed acyclic graph with two distin guished vertices s and t and with one of the following structures:
Base case: A single directed edge from s to t.
Series: The union of an s,useriesparallel graph and a u,tseries parallel graph that share a common vertex u but no other vertices or edges.
Parallel: The union of two smaller s,tseriesparallel graphs with the same source s and target t, but with no other vertices or edges in common.
Every s, tseriesparallel graph G can be represented by a decomposition tree, which is a binary tree with three types of nodes: leaves which corresponding to edges in G, series nodes which correspond to vertices other than s and t, and parallel nodes. The same seriesparallel graph could be represented by many dierent decomposition trees.
a SupposeyouaregivenadirectedgraphGwithtwospecialverticessandt. Describe and analyze an algorithm that either builds a decomposition tree for G or correctly reports that G is not s, tseriesparallel. Hint: Build the tree from the bottom up.
l
Exercises
ge abfi
h selt
cdjk
ad
fj bcik
gh
Figure .. A seriesparallel graph and a corresponding decomposition tree. Squares in the decom position tree are leaves; diamonds are parallel nodes.
b Describe and analyze an algorithm to compute a maximum s, tflow in a given s, tseriesparallel flow network with arbitrary edge capacities. Hint: In light of part a, you can assume that you are actually given the decomposition tree. First compute the maximumflow value, then compute an actual maximum flow.
. We can speed up the EdmondsKarp fattest path algorithm, at least for networks with small integer capacities, by relaxing our requirements for the next augmenting path. Instead of finding the augmenting path with maximum bottleneck capacity, we find a path whose bottleneck capacity is at least half of maximum, using the following capacity scaling algorithm. This algorithm was actually proposed by Edmonds and Karp.
Assume all the edge capacities are positive integers less than U2k for some integer k. The scaling algorithm maintains a bottleneck threshold ; initially, we setU. In each phase, the algorithm augments along paths from s to t in which every edge has residual capacity at least . When there is no such path, the phase ends, we setb2c, and the next phase begins. The algorithm ends when 0.
a How many phases will this algorithm execute in the worst case?
b Let f be the flow at the end of a phase for a particular value of . Prove thatthecapacityofaminimumcutintheresidualgraphGf isatmost E.
c Prove that in each phase of the scaling algorithm, there are at most 2E augmentations.
d What is the overall running time of the capacity scaling algorithm?
Reviews
There are no reviews yet.