L11_MaximumFlow

Over the next four lessons, we will discuss two very important problems: finding a maximum flow in a graph and solving a linear programming optimization. These problems are P-complete, meaning that any problem that can be solved on a Turing machine in polynomial time can be turned into one of these problems. We will also

Charles Brubaker and Lance Fortnow

Maximum Flow - (Udacity)

Introduction - (Udacity, Youtube)

Over the next four lessons, we will discuss two very important problems: finding a maximum flow in a graph and solving a linear programming optimization. These problems are P-complete, meaning that any problem that can be solved on a Turing machine in polynomial time can be turned into one of these problems. We will also see an important restricted case in the bipartite matching problem and then will explore the connections among these problems in a discussion of the principle of Duality, which is the inspiration for a large class of approximation algorithms.

In this first lesson, we discuss the problem of finding a maximum flow through a network. A network here is essentially anything that can be modeled as a directed graph, and by flow, we mean the movement of some stuff through this medium–from a some designated source to a destination. Typically we want to maximize the flow. That is to say, we want to route as many packets as possible from one computer across a network to another, or we want to ship as many items from our factory to our stores. Even if we don’t actually want to move as much as possible across our network, understanding the maximum flow can give us important information. For instance, in communication networks, it tells us something about how robust we are to link failures. And even more abstractly, maximum flow problems can help us figure things that seem unrelated to networks, like which teams have been eliminated from playoff contention in sports.

Given the variety and importance of these applications, it’s should be no surprise that maximum flow problems have been studied extensively, and we have some sophisticated and elegant algorithms for solving them. Let’s dive in.

Flow Networks - (Udacity, Youtube)

We begin with a definition. A flow network consists of among other things, a directed graph \(G.\) We’ll disallow antiparallel edges (i.e. \((u,v)\) and \((v,u)\) can’t both be in the graph) to simplify some of the equations. This is not a serious limitation.

We’ll distinguish two special vertices: a source typically labeled \(s\)–this is where whatever is flowing through the network starts from–and a sink typically labeled \(t\)–this is where whatever is flowing ends up. We call all other vertices internal. To keep our equations a little simpler, we’ll assume that there are no incoming edges to the source and no outgoing edges from the sink.

Associated with every pair of vertices is a capacity, which indicates how much flow it is possible to send directly between two vertices. We’ll assume that these capacities are nonnegative integers. This will make some of the arguments easier and it’s not a serious limitation. In fact, the last algorithm we see will overcome it. Also note that if there is no edge in the graph then the capacity is defined to be zero. That’s the flow network.

The flow itself is a function from pairs of vertices to the nonnegative integers, say \(f: V \times V \rightarrow Z^+.\) By this definition, the flow must be nonnegative. It also can’t exceed the capacity for any pair of vertices. That is to say,

\[ f(u,v) \leq c(u,v).\]

Also, we require that between any two vertices at least one direction of the flow be zero.

\[ f(u,v)f(v,u) = 0.\]

It doesn’t make sense to have flow going from one vertex to another and right back again.

Lastly, we require that flow be conserved at every internal vertex. We define

\[f^{\mbox{in}}(v) = \sum_{u\in V} f(u,v)\]

to be the flow into a vertex and

\[f^{\mbox{out}} = \sum_{u\in V} f(v,u)\]

to be the flow out and we require the two to be equal

\[ f^{\mbox{in}}(v) = f^{\mbox{out}}(v) \]

for every internal vertex \(v\).

For example in the lower left node of the diagram below,

we have \( 4 + 2 = 6\) units of coming in and \(5+1=6\) units of flow going out. Intuitively, this just means the internal nodes can’t generate or absorb any of the stuff that’s flowing. Those are the jobs of the source and the sink.

The overall value of the flow is defined as the flow going out of the source or equivalently the flowing going into the sink.

\[v(f) = \sum_{u \in V} f(s,u) = \sum_{u \in V} f(u,t).\]

Fill In the Flow - (Udacity)

Now, we’ll do a quick exercise to sharpen our understanding of these rules for the flow. Fill in the blanks with the appropriate numeric value.

Tricks of the Trade - (Udacity, Youtube)

In our definitions so far, we’ve limited our flow networks in several ways to make our treatment of them a little simpler. Before going any further, I want to show some tricks of the trade that allow all of the theorems and algorithms that we’ll study to be applied to more general networks.

One such limitation is the need for all of the capacities on the edges to be integers. We can extend all our arguments to all rational capacities just by multiplying the capacities by the least common multiple of denominators to create integer capacities. This just amounts to a change of units in our measurement of flow.

Another limitation we’ve imposed is that no antiparallel edges are allowed in the network. This forces us to choose a direction for the the flow between every pair of vertices. In general, however, it might not be clear in which direction the flow should go before solving the maxflow problem. It’s possible to cope with this problem with some slightly less elegant analysis, or just to convince yourself that the theorems still hold, you can add an artificial vertex between the the two nodes and route the reverse flow through there.

Another limitation of our model is that we’ve limited ourselves to single source, single sink networks. At first it might seem that we couldn’t handle a network like this one which has two sources and three sinks. Actually, however, this situation is quite easy to deal with. We can just add an artificial source node and connect that to the others with an infinite capacity and similarly add an artificial sink.

So don’t let that little limitation trouble you either.

Residual Networks - (Udacity, Youtube)

Everything we’ve done so far has been to set up the rules of the game. We’ve defined a network and the notion of a flow over it, and we’ve justified some of the simplifications we’ve made. Now, we are going to turn to the task of actually finding a maximum flow.

The search will be an incremental one. We’ll start with a suboptimal flow and then look for a way to increase it. Suppose that we are given a particular flow over a network and we want explore how we might change it.

Perhaps, we realize that we increase the flow by routing it through this just the top and bottom paths and leaving out the middle. This is equivalent to adding a flow that goes like the one shown in orange.

Notice that the flows through the middle cancel out. By adding this flow to original, we get the desired result.

Alternatively, if we just wanted to re-route the flow through the top link we could add a circular flow which would then re-route the flow.

In fact, all possible changes that we might make to our original flow can be characterized as another flow–only different rules apply. Certainly, if we’ve used up some of the capacity on an edge, we can’t use the full capacity in the flow we’re going to add.
We capture the rules for the flow that we are allowed to add with the notion of a residual flow network. We start by defining the residual capacity for all pairs of vertices.

If there is an edge between the pair, then the residual capacity is just however much capacity is left over after our original flow uses up some of it. For reverse edges, the capacity is however much flow went over the edge in the opposite direction. We can just “unsend” this much flow. Everywhere else the residual capacity is zero.

The edges of our residual network are just the places where the residual capacity is positive. Keeping the network sparse helps in the analysis.

Find the Residual Errors - (Udacity)

Now for a quick exercise on residual networks. Consider the flow over the flow network on the left, and I want you to mark the edges with errors in this attempt at a residual network on the right.

Augmentations - (Udacity, Youtube)

Ultimately, as we try to find a maximum flow we are going to start with a suboptimal flow and the augment it with a flow we find in the residual network. Let’s see how this works. We’ll start with a flow \(f\) in \(G.\) Then drawing the residual network, we’ll let \(f'\) be a flow there.

Of course, it obeys the residual capacity contraints. Then, we can add these two flows together using this special definition.

\[(f+f')(u,v) = \left\{\begin{array}{ll} f(u,v) + f'(u,v) - f'(v,u) & \mbox{if}\; (u,v) \in E\\\\ 0 & \mbox{otherwise} \end{array}\right.\]

Note only one of the values from \(f'\) can be positive in the \((u,v) \in E\) case.

Now, I claim without proof that

The augmented flow \(f+f'\) is a flow in the original network \(G\) and that it’s value is just the sum of the values of the two individual flows.

This is pretty easy to verify with the equations, but it’s not very illuminating, so we’ll skip it here and focus on the intuition instead. Is this augmented flow a flow in original network \(G\)? It fits within the capacity constraints, essentially by construction of the residual capacities. And it and conserves flow because both \(f\) and \(f'\) do. So, yes it is a valid flow.

The flow out from the source is a simple sum, which makes it a linear function, so yes it makes sense that the flow value of the sum should be the sum of the flow values as well.

The Ford-Fulkerson Algorithm - (Udacity, Youtube)

With all of this notation and background behind us, we are ready for the Ford-Fulkerson method. As we’ll see, it’s not really specific enough to merit being called an algorithm though we’ll sometimes call it that anyway.

We begin by initializing the flow to zero. Then, while there is a path from the source \(s\) to the sink \(t\) in the residual graph, we are going to calculate the minimum capacity along such a path and then augment with a flow that has this value along that path.
Once there are no more paths in the residual graph, we just return the current flow that we’ve found \(f\).

Let’s see how this works on a toy example. [See Video]

Does the algorithm terminate? Remember that the capacities are all integral, so each augmenting flow \(f'\) has to have value at least \(1;\) otherwise, the path wouldn’t be in the graph. Therefore, we can’t have more iterations than the maximum value for a flow. So, yes it terminates.

How much time does it spend per iteration? Finding a path can be done with breadth-first search or depth-first search in time proportional to the number of edges. Constructing the residual graph also takes this amount of time, as it has at most twice the number of edges of the original graph. And, of course updating the flow requires a constant amount of arithmetic per edge. All-in-all then, we have just \(O(|E|)\) time for each iteration–that is time proportional to the number of edges.

This is a good start for the analysis, but it leaves us with some unanswered questions. Most important, perhaps, is whether the returned flow is a maximum flow. Sure it’s maximal in the sense that we can’t augment it any further, but how do we know that with a different set of augmenting paths or perhaps with an entirely different strategy altogether that we wouldn’t have ended up with a greater flow value?

Also, this bound on the number of iterations is potentially exponential in the size of the input, leaving us with an exponential algorithm. Perhaps, there is some way to improve the analysis or revise the algorithm to get better runtime.

These two questions will occupy the remainder of the lesson. We’ll start with showing that Ford-Fulkerson does indeed produce a maximum flow and then we’ll see about improving the running time.

Flows and Cuts - (Udacity, Youtube)

If your intuition tells you that the incremental approach of the Ford-Fulkerson method produces a maximum flow, that’s a good thing. Your intuition is correct. But it’s important that it be correct for the right reasons. Not all incremental approaches work. Often in optimization, we get stuck in local minima or local maxima. We need to argue either that we never make a mistake–analysis of greedy algorithms typically have this feel–or we need to be able argue that the rules for incrementing allow us to undo any mistakes that may have made along the way. The latter will be the case for maximum flow.

The argument we’ll make is complex and will require us to introduce a new notion of a minimum cut in a graph along the way, but in the end it is rewarding and provides an example of how to find elegance in analysis.

So far, we know that the network will have some possible nonnegative flow values but it’s not exactly clear how high this range goes or where the results of Ford-Fulkerson fit in. One observation is that the flow value can’t exceed the capacity of the edges coming out of the source. Remember that the flow value is defined to be the sum of the flows over these edges. Separating \(s\) from \(t\) in this way constitutes a cut in the graph, which as we’ll see is an upper bound on the value of any flow.

It’s possible that there will be smaller cuts as well, which will shrink the range of possible flow values for us.

Even better, however, we’ll see that the flow produced by Ford-Fulkerson has the same value as a cut, and since this cut serves as an upper bound on all possible flows, this flow must be a maximum. In other words, the two arrows in the diagram will meet at the value of the flow produced by Ford-Fulkerson. That’s we’re this argument will end up.

Cut Basics - (Udacity, Youtube)

We start with making a more precise definition of an \(s\)-\(t\) cut, saying that

A cut it is a partition \((A,B)\) of the vertices such that the source \(s\) is in the set \(A\) and the sink \(t\) is in the set \(B\).

For example, in this network here, the green nodes might be in \(A\) and the orange ones in \(B\).

Or we might have this cut here.

The vertices within one side of the partition don’t have to be connected in the definition.

Next, we observe that if \(f\) is an \(s\)-\(t\) flow and \((A,B)\) is an \(s\)-\(t\) cut, then the value of the flow is the flow out of \(A\) minus the flow into \(A\), or equivalently, the flow into \(B\) minus the flow out of \(B\).

\[v(f) = f^{\mbox{out}}(A) - f^{\mbox{in}}(A) = f^{\mbox{in}}(B) - f^{\mbox{out}}(B).\]

For this first cut shown above, we have \(2 + 6\) entering and 2 leaving for a total of 6. For the second cut shown, we have \(1 + 1 + 5 + 1\) units exiting \(A\) and \(2\) units entering for a total of 6, which is indeed the flow.
As you might imagine the proof comes from the conservation of flow. We start with the definition of the flow and then add a zero in the form of the conservation equation for each node in \(A\).

For every edge where both vertices are in \(A\) terms cancel, leaving us with just the outgoing edges from \(A\) to \(B\) and the incoming edges from \(B\) to \(A\). And these sums then are just the flows out and flows into \(A\) as stated by the theorem. Check this for yourself with the equations.

Cut Capacity - (Udacity, Youtube)

From this notion of a cut, it is natural to think about, “how much flow could possibly come across the cut?” Clearly, it can’t exceed the sum of the capacity of the crossing edges. This intuition gives rise to the idea of the capacity of a cut, which is just the sum of the capacities of edges crossing over from \(A\) into \(B.\)

\[c(A,B) = \sum_{u\in A, v\in B} c(u,v).\]

Cut Capacity Calculation - (Udacity)

Let’s do a quick exercise on cut capacity. What is the capacity of the cut shown in the above flow network?

Cut Capacity Continued - (Udacity, Youtube)

Intuitively, it should be clear that the capacities of \(s\)-\(t\) cuts represent upper bounds on the amount of flow that could go from \(s\) to \(t.\) We state this as the following lemma

Let \(f\) be a flow and let \((A,B)\) be an \(s\)-\(t\) cut in a flow network. Then

\[ v(f) \leq c(A,B).\]

The proof goes like this. The value of the flow is the flow out of the set \(A\) minus the flow into the set \(A.\)

\[ v(f) = f^{\mbox{out}}(A) - f^{\mbox{in}}(A).\]

We can just drop this second second term, leaving us with just \(f^{\mbox{out}}(A).\)

\[ v(f) \leq f^{\mbox{out}}(A) = \sum{u\in A, v \in B} f(u,v).\]

This is bounded by the capacities on the edges crossing the cut, and this sum is then the capacity of a cut.

\[ v(f) \leq \sum{u\in A, v \in B} f(u,v) \leq \sum{u\in A, v \in B} c(u,v) = c(A,B).\]

Note from this proof that the inequality will be tight when there is no flow re-circulating back into \(A\) and all the crossing edges are saturated–i.e. the flow is equal to the capacity. Keep this in mind.

The Max-Flow Min-Cut Theorem - (Udacity, Youtube)

We are now ready for the climactic big theorem of this lesson, the Max-Flow Min-cut Theorem.

The following are equivalent:

  • \(f\) is a maximum flow in \(G.\)
  • \(G_f\) has no augmenting paths.
  • There exists an \(s\)-\(t\) cut \((A,B)\) such that \(v(f) = c(A,B).\)
  • This is the realization of the strategy outlined earlier, where were going to introduce the notion of the cut, show that it served as an upper bound the on flow, and then show that Ford-Fulkerson produced a flow with the same value as a cut.

    As an immediate corollary we have then that

    The Ford-Fulkerson approach returns a maximum flow.

    Let’s see the proof of the Max-Flow Min-Cut theorem. We start by showing that if \(f\) is a maximum flow in a network, then it has no augmenting paths in the residual network. Well, suppose not, and let \(f'\) be an augmenting flow.
    Then we can augment \(f\) by \(f'\) and the flow of the sum will be the sum of the flows. The value of the augmenting flow is positive, so we have created a new, greater flow contradicting the the fact that \(f\) was a maximum flow.

    \[v(f+f') = v(f) + v(f') > v(f).\]

    Next, we show that the fact that the residual network has no augmenting paths implies that there is an s-t cut that has the same capacity as the flow. This is real heart of the theorem.

    Let \(A\) be the set of vertices reach from the source \(s\) in the residual network, and let \(B\) be all the other vertices.

    Flows Across the Cut - (Udacity)

    We’ll make the next step in the proof an exercise. If \((u,v)\) goes from \(A\) to \(B,\) what does that implies about the flow. Similarly, if it goes from \(B\) to \(A,\) what does that imply about the flow. Answer both questions.

    The Max-Flow Min-Cut Theorem Continued - (Udacity, Youtube)

    We have concluded that any forward edge from \(A\) to \(B\) must be saturated and any backward edge from \(B\) to \(A\) must be unused.
    Before going any further, let’s illustrate this with an example. Here we have a flow on the left and the corresponding residual graph on the right.

    Note that there are no path from \(s\) to \(t\) in the residual graph. The vertices that can be reached from \(s\) are marked as green and the other ones as orange. It’s easy to see that all the edges from the green to the orange vertices are saturated, and the edges from the orange to the green are empty, just like the theorem claims.

    Recall that for any cut the value of a flow is the flow out of the partition with the source minus the flow into the partition with the source.
    As, we’ve just argued, however, in this case there is no flow back into the source partition. Moreover, the flow out saturates all the edges, so it’s just the sum of the capacities across the cut, which is then defined as the cut capacity.

    \[ v(f) = \sum{u\in A, v \in B} f(u,v) = \sum{u\in A, v \in B} c(u,v) = c(A,B).\]

    That completes that part of the theorem.

    Lastly, we need to show that the existence of a cut with the same capacity as a flow shows that the flow is a maximum one. This follows immediately from our earlier argument that the cut capacity is an upper bound on the max-flow. There can’t be a bigger one or it would violate the bound.

    That then completes the theorem. These three things are equivalent. Maximum flow is equal to the minimum capacity cut, and the Ford-Fulkerson approach returns a maximum flow.

    If you followed all of that, congratulations! The max-flow/min-cut theorem is one of the classic theorems in the study of algorithms and a wonderful illustration of duality, which we’ll discuss in a later lesson. For now, however, we are not quite ready to leave maximum flow yet.

    Bad Augumentations - (Udacity)

    So far, we’ve show that Ford-Fulkerson does in fact produce a maximum flow. Now, we turn to the question of it’s running time. Recall that the only bound we have so far on the number of iterations is the value of the flow itself, since each augmentation must increase the flow value by one.

    Let’s see if this bound is tight. Consider the flow network below and give the maximum number of augmenting paths that Ford-Fulkerson might find.

    Better Augumentations - (Udacity, Youtube)

    Obviously, we made some pretty poor choices for picking the augmenting paths. One idea for picking better paths is to prefer heavier ones. Another is to prefer shorter paths. Note that the poor choices of paths here were the longer ones.

    Scaling Algorithm - (Udacity, Youtube)

    This idea that we should prefer heavier flows brings us to the scaling algorithm.If heavy flows are good, why not choose the heaviest possible flow. We could do this by starting with an empty graph and then adding the edge with the largest remaining residual capacity until there was an \(s\)-\(t\) path, but this would be unnecessarily slow. Instead, we fix a schedule of thresholds for the residual capacity and lower the threshold when there are no more augmenting paths in the residual network.

    We’ll start by defining the residual network with threshold \(\Delta\) to include only those edges whose residual capacity exceed \(\Delta.\)

    \[ G_f(\Delta) = (V,\{(u,v) : c_f(u,v) \geq \Delta\}).\]

    Note that when \(\Delta\) is \(1\) this is equivalent to the traditional residual network. Then we can state the algorithm as follows. We initialize the flow to be zero and the parameter Delta to be this trivial upper bound on the flow in a single path.

    Then while \(\Delta \geq 1\), we look for an augmenting path \(p\) in \(G_f(\Delta)\) and use it to augment the flow. Once all such paths are exhausted, we cut \(\Delta\) in half.

    Some of the analysis, we can do just by inspection. Letting \(C\) be the initial value for \(\Delta,\) we see that we use \(O(\log C)\) iterations of the outer loop.

    The steps of the inner loop cost only \(O(|E|)\) time.

    The big question then is how many iterations of this inner loop are there?

    Analysis of Scaling - (Udacity, Youtube)

    Here, we will prove that

    The maximum number of iterations for a scaling phase is at most \(2|E|\).

    The key lemma will be that

    If \(G_f(\Delta)\) has no \(s\)-\(t\) paths, then there is an \(s\)-\(t\) cut \((A,B)\) such that \(c(A,B) \leq v(f) + |E|(\Delta - 1).\)

    The proof will feel a lot like the max-flow min-cut proof. We let \(A\) be the set of vertices reachable from \(s\) in \(G_f(\Delta)\) and we let \(B\) be the complement of this set in \(V\). Edges from \(A\) to \(B\) in this graph must have residual capacity at most \(\Delta - 1\),

    \[(u,v) \in A \times B \Longrightarrow c(u,v) - f(u,v) \leq \Delta - 1.\]

    and edges from \(B\) to \(A\) can’t have flow more than \(\Delta - 1\) or else the reverse edge would appear in the graph

    \[(u,v) \in B \times A \Longrightarrow f(u,v) \leq \Delta - 1.\]

    The flow is then

    \[ \begin{eqnarray} v(f) & = & \sum_{(u,v) \in A \times B} f(u,v) - \sum_{(u,v) \in B \times A} f(u,v) \\\\ & \geq & \sum_{(u,v) \in A \times B} c(u,v) - (\Delta - 1) - \sum_{(u,v) \in B \times A} (\Delta-1) \\\\ & \geq & c(A,B) - |E|(\Delta-1). \end{eqnarray} \]

    With this lemma complete, we now return to the main claim we want to prove.

    The base case where \(\Delta = C\) is trivial. Here there can be only at most one iteration. For subsequent iterations, we let \(f\) be the flow after a phase of \(\Delta\) augmentations and let \(g\) be the flow before, which would be after a phase of \(2\Delta\) or or a phase of \(2\Delta + 1\) augmentations.

    The flow \(f\) is a most the maximum flow, but this is at most the capacity of the \(s\)-\(t\) cut induced by the graph \(G_f(2\Delta+1)\) from the previous iteration. Our lemma then says

    \[v(f) \leq v(f^*) \leq c(A,B) \leq v(g) + 2\Delta.\]

    Now let \(k\) be the number of iterations used to go between \(g\) and \(f.\) Each iteration increased the flow by at least \(\Delta,\) so

    \[k \Delta \leq v(f) - v(g) \leq 2|E|\Delta,\]

    Hence, \(k \leq 2|E|\): we can have used at most 2|E| iterations.

    This then completes the analysis of the scaling algorithm. We have at most \(\log C\) iterations of the outer loop, \(O(E)\) iterations of the inner loop with each one costing \(O(|E|)\) time. The total is then \(O(|E|^2 \log C).\)

    The Edmonds-Karp Algorithm - (Udacity, Youtube)

    So far we’ve explored the idea that we should prefer heavier augmenting paths. It turns out that the idea of using shorter paths also gives rise to an efficient algorithm. This is the Edmonds-Karp algorithm, also discovered independently by Dinic in the Soviet Union. This is exactly Ford-Fulkerson, only we are sure to choose a minimum length path.

    The cost of an iteration is \(O(|E|)\) as always, as we just use bread-first-search to the shortest s-t path. If we can bound the number of iterations, most tightly we’ll have a better found than for the naive Ford-Fulkerson. Indeed we will be able to bound it to be at most |V||E|, showing that

    The Edmonds-Karp returns a maximum flow in \(O(|E|^2|V|)\) time.

    Analysis of Edmonds-Karp - (Udacity, Youtube)

    Now for the analysis. Mostly, I’ll just try to share the intuition. We want to show that only \(O(|V||E|)\) augmentations are used.
    To see this, we define something called a level graph. In a formal way, we say that

    The level of a vertex \(v\) is the shortest path distance from the source vertex \(s.\)

    We denote the level of a vertex \(v\) as \(\ell(v).\)

    The level graph is the subgraph of the original graph that includes only those edges from one level to one higher, i.e. edges \((u,v) : \ell(v) = \ell(u) + 1.\)

    A graph and the corresponding level graph are shown below would be this subgraph down here.

    Three edges have been deleted because they go between vertices of the same level or back up a level.

    We first observe that augmenting along a shortest path only creates paths that are longer ones. Say that we push flow along the topmost path as shown below.

    This introduces back edges along the path. Note, however, that these back edges are useless for creating a path of the same length. In fact, because they go back up a level, any path that uses one of them must use two more edges that the augmenting path we just used.

    Next, we observe that the shortest path distance must increase every \(|E|\) iterations. Every time that we use an augmenting path we delete an edge from the level graph, the one that got saturated by the flow.
    From our example, suppose that the middle edge was saturated in an augmentation along this path.

    This edges won’t come back into the level graph until the minimum path length is increased. As we’ve already argued the reverse edges are useless until we are allowed to use longer paths.

    Lastly, there are only \(|V|\) possible shortest path lengths, so that completes the theorem.

    Notice that with the Edmonds-Karp time bound of \(O(E^2V),\) we’ve eliminated the dependence of the running time on the capacities. This means that the algorithm is now strongly polynomial, and actually we can eliminate the requirement that the capacities be integers entirely.

    Dinic’s Algorithm - (Udacity, Youtube)

    There is one more refinement to the algorithm that I can’t resist and that is due to Dinic. He actually published his algorithm in 1970, two years before Edmonds-Karp.

    His key insight is that the work of computing the shortest path can be recycled so that a full recomputation only needs to happen when the shortest path distance changes, not for every augmenting path.

    As with all augmenting flow-based strategies, we start with an initial flow of zero. Then we repeat the following. We build a level graph from the residual flow network, and let \(k\) be the length of a shortest path from \(s\) to \(t.\) Then while there is a path from source to sink that has this length \(k,\) we use it to augment the flow and then update the residual capacities.
    Then we repeat this until there are no more \(s\)-\(t\) paths and we return the current flow.

    Turning to the analysis, we’ll call one iteration of this outer loop a phase, and we’ll be able to argue that each phase increases the length of the shortest \(s\)-\(t\) path in the residual network by 1. The principle here is the same as for Edmonds-Karp: augmenting by a shortest path flow doesn’t create a shorter augmenting flow. Hence, once we have exhausted all paths of a given length, the next shortest path must be one edge longer. Hence there only \(O(|V|)\) phases.

    Within a phase the level graph is built by bread-first-search so that costs only \(O(|E|).\)

    The hardest part of the argument will be that this loop altogether takes only \(O(EV)\) time. We’ll see this argument in a second.

    Altogether, we will show that Dinic’s algorithm takes \(O(|E||V|^2)\) time which is an improvement upon Edmonds-Karp \(O(|E|^2|V|)\) time.

    Analysis of Dinic’s Algorithm - (Udacity, Youtube)

    We turn to the key part of the analysis where we show that each phase takes \(O(VE)\) time. As with Edmonds-Karp we will use a level graph. In this case, however, the algorithm actually builds the graph, whereas in Edmonds-Karp we simply used it for analysis. The level graph can be built by running breadth-first search and saving all forward edges, while ignoring backwards and lateral ones.

    When we augment the flow along a path, say along the topmost path, we introduce reverse edges into the residual graph. Recall that these are always backwards edges in the level graph and hence aren’t useful in building a path equal to or shorter than the previous shortest path. Well, if the new edges are useless, why rebuild the level graph of \(G_f\) when the old one will serve just as well? We can just update the residual capacities.

    More precisely, given the possibly outdated level graph, we can build a path from the source just by making the first vertex on the adjacency list the next vertex on the path.

    • If this generates a path to \(t,\) then we augment the flow and update the residual capacities.

    If it doesn’t, then we delete the last vertex in the path from the level graph.

    In this example, we would first find a path from from \(s\) to \(t,\) and maybe the middle edge is the bottleneck. It’s capacity gets set to zero and it gets deleted.Next, we would build a path again from s, and this time, we would run into a dead-end. So we delete, this vertex and continue.

    There are only V vertices in the graph, so we can’t run into more than V dead-end, and every augmentation deletes the bottleneck edge and we can’t delete more than E edges. Overall, then we won’t try more than E paths.

    The process of building these paths and augmenting flows is just proportional to the path length, however. Making the overall time cost of a phase just O(VE).

    Taking this altogether, we have \(|V|\) phases each costing \(O(|V||E|)\) time for a total of \(O(|V|^2 |E|)\) time as desired.

    Conclusion - (Udacity, Youtube)

    We have now seen a few improvements to the naive version Ford-Fulkerson method, but this isn’t the end of the story. There are some even more sophisticated approaches that improve the runtime even further also based on the idea of augmenting flows. There is also a family of algorithms called push-relabel that allow internal vertices to absorb flow during intermediate phases of the algorithms. In practice, these seem to perform the best.

    Beyond the just seeing algorithms in this lesson, we examined the max-flow min-cut theorem. This was more than just a trick for proving the correctness of Ford-Fulkerson. It’s part of a larger pattern of Duality that provides important insight in a variety of contexts. We’ll explore this more fully in our lesson on Duality.

    ncG1vNJzZmirY2Ourq3ZqKWar6NjsLC5jpymp6yVo8FvwcOamqKsqWKxosDAZ5qopV%2BYvLa%2B0p6qaJ%2BkYrC0gpRpbGilka22rsHMn6Oor16dwa64

     Share!