ud557 »

Computability and Algorithms - Course Notes


Contents


In school, it is common to develop a certain mental conception of a function. This conception is often of the form:

A function is a procedure you do to an input (often called x) in order to find an output (often called f(x)).

However, this notion of a function is much different from the mathematical definition of a function:

A function is a set of ordered pairs such that the first element of each pair is from a set X (called the domain), the second element of each pair is from a set Y (called the codomain or range), and there are no two pairs with the same domain element.

The first conception---the one many of us develop in school---is that of a function as an algorithm: a finite number of steps to produce an output from an input, while the second conception---the mathematical definition---is described in the abstract language of set theory. For many practical purposes, the two definitions coincide. However, they are quite different: not every function can be described as an algorithm, since not every function can be computed in a finite number of steps on every input. In other words, there are functions that computers cannot compute.

This is a fuzzy claim that requires more rigorous definitions before we can make it precise. We said a function is computable if there is an "algorithm" that takes a finite number of steps to generate an output from an input, but what is an "algorithm"? How can we make this more precise?

Let us set aside functions for a moment and try to formalize the notion of computation. We will imagine a very specific type of machine: a machine that takes an input and either accepts or rejects the input (in other words, its output is binary: 0/1, no/yes, false/true). The inputs read by the machine must be in the form of strings of characters from some finite set, called the machine's alphabet. For example, the machine's alphabet might be binary (0s and 1s), it might be based on the genetic code (with symbols A, C, G, T), or it might be the ASCII character set.

A language, in general, is any set of strings over some alphabet. We will define a computable language to be the set of all strings from its alphabet that some machine accepts. (If we call the machine M, then the language of M is usually denoted L(M).) So if M is a machine whose alphabet is {0,1} and which accepts binary strings with an even number of 0s and rejects all other binary strings, then L(M) = {binary strings with an even number of 0s}, and therefore this language is a computable language.

In this way, a machine's language determines a function whose domain is the set of strings over an alphabet Σ and whose range is the finite set {ACCEPT,REJECT}. A function of this type that is determined by the language of some machine is called a computable function.

The concept of a language is fundamental to this course, so we take a moment to describe common operations used to manipulate languages.

Since languages are sets of strings, when we talk about languages, it is almost always in the context of a fixed alphabet from which the letters of the strings are drawn. For this section, we'll call this fixed alphabet Σ. The set of all possible strings with letters from Σ is denoted Σ*.

The usual notions of union, intersection, and complementation apply to languages. Two other operations are also used. The first is concatenation. If L and L' are languages, then

LL' = {xy : x is a string in L and y is a string in L'}.

In other words, the concatenation of two languages is the set of strings formed by taking a string from the first language and concatenating a string from the second language to its end.

We can denote the concatenation of a language with itself by L2, as well as the k-fold concatenation of L with itself by Lk. As a special case, L0 is the set containing just the empty string.

The second major operation used with formal languages is the Kleene star. We define

L* = L0LL2L3 ∪ ...

In other words, L* contains every string that can be formed by concatenating together zero or more strings from L.

We need one more piece of mathematical background before we can more formally prove our claim that not all functions are computable. Our proof will essentially show that there are more languages than there are possible machines. This requires us to be able to tell a difference in size between infinite sets, since there are infinitely many possible languages and infinitely many possible machines.

Let us make the following definition:

A set S is countable if it is finite or if it is in one-to-one correspondence with the natural numbers.

By one-to-one correspondence, we mean that there is a function from S to the nonnegative integers such that every nonnegative integer is mapped to by exactly one element of S. Some examples of infinite countable sets (also called countably infinite sets) are:

  • The set of nonnegative even numbers (a one-to-one correspondence to the natural numbers is f(x) = x/2)
  • The set of positive odd numbers (with correspondence f(x) = (x-1)/2
  • The set of all integers (with correspondence f(x) = 2x if x is nonnegative and f(x) = -2x - 1 if x is negative)
  • The set of all pairs of integers (exercise left for the reader!)
  • The set of all rational numbers (exercise left for the reader! For a hint: try using the correspondence between all pairs of integers and the natural numbers.)

If an infinite set has no such one-to-one correspondence with the natural numbers, then we call that set uncountable (or uncountably infinite). The intuition is that, in some sense, uncountably infinite sets are "larger" than countably infinite sets: they are too large to be put into correspondence with the natural numbers.

Existence of Uncomputable Functions

To show that not all functions are computable, we'll start by showing that the set of all possible machines is countably infinite. First, we'll show that if Σ is a finite set, then Σ* (the set of all strings with letters in Σ) is a countably infinite set. To see this, order the strings in Σ* by dictionary order, with shorter strings before longer strings. (For our purposes, let's 0-index this ordering, so that the 0th string is the empty string, then come the strings with one letter, then the strings with two letters, and so on.) Then the correspondence between Σ* and the natural numbers is given by f(x) = the position of x in this ordering.

We haven't finished formally defining "computation" or "algorithm" yet: we'll do that in the next lesson. For now, let's take it on faith that an algorithm can be encoded by a finite string from an alphabet (for example, a valid Python program that takes a string as input and outputs "True" or "False", written using the alphabet Σ of ASCII characters). Since there are only countably many strings in Σ*, there can only be countably many algorithms.

On the other hand, consider the number of possible languages over Σ: that is, the number of subsets of Σ*. We will show that the set of languages is uncountably infinite. This will be a proof by contradiction. Suppose there are countably many languages over Σ. Then we can order all the languages in a sequence: L0, L1, L2, etc. Also order the strings in Σ* using the dictionary order like we did before, and call the strings x0, x1, x2, etc.

Now consider the language L', defined in the following way: xi is in L' if and only if xi is not in Li. L' is a valid language, since it is a subset of Σ*.  However, it cannot equal L0, since if it did, then x0 would be in L' if and only if x0 is not in L', a contradiction. Similarly, L' cannot equal L1, L2, L3, etc. Thus, L' is not in the list of all languages over Σ, but that itself is a contradiction since we assumed all the languages had been ordered like that. The conclusion is that the set of languages over Σ could not have been ordered, and therefore there are uncountably many languages over Σ.

To conclude, we note that there are uncountably many languages, but only countably many algorithms. Since each algorithm has only one language it can compute, there are more languages than there are algorithms to compute them. Thus, there are uncomputable languages and therefore uncomputable functions.


Turing Machines


The Church-Turing Thesis


Universality


Undecidability


P and NP


Dynamic Programming


The Fast Fourier Transform


In this lesson, we will discuss the problem of finding a maximum flow in a network. This problem is P-complete, meaning that any problem that can be solved on a Turing machine in polynomial time can be transformed into a of problem of this form. A network is essentially anything that can be modeled as a directed graph; by a flow, we mean the movement of some material through this network--from a designated source to a destination. Typically we want to maximize the flow: 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.

Review of Graphs and Graph Traversals

For this lesson, you will need to be familiar with a few basic mathematical properties of graphs. We will review those concepts briefly here. If you'd like some more in-depth resources for these concepts at the level needed for this class, please see [insert resources here].

First, some definitions:

An undirected graph G is an ordered pair (V,E), where V is a set (called the vertices of G), and E is a set of unordered pairs of vertices (called the edges of G).

We sometimes use V(G) to represent the set of vertices of G and E(G) to represent the set of edges of G. Note that this definition does not permit loops (an edge with only one endpoint) or multiple edges between vertices.

A directed graph (or digraph) D is an ordered pair (V,E), where V is a set (again called the vertices of D), and E is a set of ordered pairs of vertices (again called the edges of D).

The difference between the two definitions is that the vertices determining the edges have no ordering in an undirected graph but do have an ordering in a directed graph. We usually denote this by pointing an arrow on each edge in visual representations of a directed graph. The direction of the arrow is called the orientation of the edge.

Two vertices u and v in an undirected graph G are adjacent if there is an edge between u and v in G; alternatively, if {u,v} is an element of E(G). A similar notion holds in a directed graph D: u and v are adjacent if there is an edge oriented in in either direction between u and v; alternatively, if either (u,v) or (v,u) is in E(D). An edge is incident to a vertex v if v is one of the endpoints of the edge.

For an undirected graph G, the neighbors of a vertex v are the vertices of G which are adjacent to u. The degree of v, denoted deg(v), is the number of edges incident to v, which equals the number of neighbors of v.

For a directed graph D, the in-degree of a vertex v is the number of edges incident to v which are oriented towards v, and the out-degree of v is the number of edges incident to v which are oriented away from v.

A path P in an undirected graph G is a sequence of the form (v0, e1, v1, e2, ..., en, vn) such that each vi is a distinct vertex in G (so no repeated vertices) and each edge ei is incident to both vi and vi+1. A cycle C in an undirected graph G is a sequence of the form (v0, e1, v1, e2, ..., en, vn) subject to the same constraints as a path except that v0 and vn must be the same vertex. The length of a path (resp. cycle) is the number of edges in the path (resp. cycle).

An overview of and pseudocode for depth-first search and breadth-first search can be found in this Wikipedia article.

A network consists of among other things, a directed graph D. For this course, we'll disallow antiparallel edges (that is, given two vertices u and v, at most one of the edges (u,v) or (v,u) may be present) to simplify some of the equations. This is not a serious restriction: the theory of networks and flows can be reconstructed even when allowing antiparallel edges.

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. We do not allow any incoming edges to the source or any outgoing edges from the sink.

Associated with every pair of vertices is a capacity, a nonnegative integer c(u,v) which indicates how much flow it is possible to send along the directed edge from u to v. If there is no edge from u to v, then c(u,v) is defined to be 0. Since we have no antiparallel edges in the network, this implies that either c(u,v) or c(v,u), or both, must be 0.

The flow in a network is a function from pairs of vertices to the integers, represented by f(u,v). For every pair of integers, f(u,v) = -f(v,u), and f(u,v) can't exceed the capacity for any pair of vertices: f(u,v)c(u,v) for all vertices u and v.

Lastly, we require that flow be conserved at every internal vertex: if f in(v) is the flow into a vertex v and f out(v) is the flow out of v, these must be equal. Intuitively, this means the internal nodes can't generate or absorb any of the material that's flowing through the network.

The value of a flow f is defined to be the flow leaving the source node (f out(s)); equivalently, it is the flow entering the sink node (f in(t)).

We made a number of restrictions on our abstract model for networks and flows. These restrictions simplify the calculations and arguments we will need to make to develop the theory of the model; however, it is a fair question to ask if the results we prove with these restrictions are significantly weakened when we remove the restrictions. Here, we will show how this model generalizes to models with fewer restrictions while leaving the theory intact.

One restriction we made was the need for all of the edge capacities and flows to be whole numbers. We can extend all our arguments to nonnegative rational capacities and flows in the following way: if we have a network flow with rational capacities and flows, let d be the least common multiple of all the denominators in the capacities and flows. Multiply each edge's capacity and flow by d: this leaves us a network with integer capacities and integer flows. (This essentially amounts to a change of units in our measurement of capacity and flow.)

Another restriction 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 max-flow problem. However, it's possible to transform a network with antiparallel edges into a network without such edges. If u and v have antiparallel edges, remove the edge from v to u, add an artificial vertex w, add an edge directed from v to w, and then add an edge directed from w to u. The capacity on the two new edges should both equal the capacity of the removed edge. After computing the max flow for the new network, the flow will be the same for both of the new edges. This will be the correct flow for the edge from v to u in the original network's max flow.

Another limitation of our model is that we've limited ourselves to single-source, single-sink networks. Given a network with multiple sources, we can transform it into a single-source, single-sink network in the following way: add an artificial source node s* and edges from s* to each of the sources, each with infinite capacity. Similarly, for a network with multiple sinks, add an artificial sink node t* and edges from each sink to t*, each with infinite capacity. After computing the max flow for the new network, ignore the flows on the artificial edges to obtain the max flow for the original network.

Both of the methods in the previous two paragraphs also allow us to cope with the case in which there are edges directed into the source node or away from the sink node.

Now, we turn to the task of computing finding a maximum flow in a network: that is, a flow that attains a maximum value. The search will be an incremental one: we'll start with a suboptimal flow and then look for a way to increase it.

We start by defining the residual capacity for all pairs of vertices. Given a flow f on a network and an edge from u to v, the residual capacity from u to v, denoted cf(u,v), is equal to c(u,v) - f(u,v): however much capacity is left over after our original flow uses up some of it, and we define cf(v,u) to be f(u,v). For all other pairs of vertices, the residual capacity is 0.

Given a network N and a flow f on N, the associated residual network is a network defined on the same nodes as N with an edges from u to v if and only if the cf(u,v) > 0. The capacity of the edge is equal to the residual capacity.

A path from s to t in the residual network is called an augmenting path for reasons to be discussed shortly.

As we try to find a maximum flow in the network N, we start with a suboptimal flow and then augment it with a flow we find in the residual network.

Given a flow f in N, let Nf be the associated residual network, and let f' be a flow in Nf. For each edge (u,v) in Nf, increase the flow along that edge in the original network N by the flow along that edge in the residual network. In other words, make a new flow f'' in N such that f''(u,v) = f(u,v) + f'(u,v) for each edge (u,v) in the residual network.

We claim that this augmented flow f'' satisfies the conditions of a flow in the original network N, and that the value of f'' is the sum of the values of the two individual flows f and f'. We'll give a sketch of the proof here:

The augmented flow is a flow in original network N because it fits within the capacity constraints (essentially by our construction of the residual network). It also conserves flow because both f and f' do. The flow of f'' out from the source vertex is also a sum of the flows out from the source in f and f', which is by definition the sum of the values of f and f'.

Now that we've defined all the prerequisite notions we'll need, let's actually find the way to maximize the flow through a network. The method we'll discuss is the Ford-Fulkerson algorithm. The algorithm proceeds as follows:

  • Initialize a flow f on N so that f(u,v) = 0 for all vertices u,v.

  • Compute the residual network Nf.

  • While there is a path from the source s to the sink t in Nf (i.e. an augmenting path):

    • Find the edge with minimum capacity along such a path. Denote that minimum capacity by c.

    • Let f' be a flow in Nf such that f'(u,v) = c for each edge on that path and 0 for all other edges. (We call f' an augmenting flow.)

    • Augment f by f'.

    • Update the capacities of the edges in Nf.

  • Return f. This is a flow with maximum value in N.

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. Therefore, the algorithm terminates.

How much time does the algorithm 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 updating the flow requires a constant amount of arithmetic per edge. Therefore, we spend O(|E|) time for each iteration: that is, time proportional to the number of edges.

This is a good start for our analysis, but it leaves us with some unanswered questions. Perhaps most importantly: is the returned flow is a maximum flow? It is maximal in the sense that we can't augment it any further, but how do we know that we couldn't obtain a flow with greater value using a different set of augmenting paths or perhaps with an entirely different strategy altogether?

Also, the bound we obtain on the number of iterations is potentially exponential in the size of the input, leaving us with an intractable algorithm. Is there some way to improve the analysis or revise the algorithm to get a better worst-case runtime?

We will occupy ourselves with these two questions for the remainder of the lesson. We'll first show that Ford-Fulkerson does indeed produce a maximum flow, and then we'll see about improving the running time.

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 problems we can 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 we may have made along the way. The latter will be the case for Ford-Fulkerson. The argument we'll make is complex, and it will require us to introduce a new concept in graphs along the way. In the end it is rewarding and provides an example of an elegant analysis of an algorithm.

One preliminary observation is that the value of any flow in the graph can be at most the sum of the capacities of the edges coming out of the source, since the flow's value is defined to be the sum of the flows over these edges.

Suppose we remove edges from the network in such a way that we disconnect the supply line: there is no possible way to reach the sink t from the source s. (For example, we could remove the set of edges coming out of the source, since removing those edges leaves no path from the source to the sink.) Since all the material that starts in the source must pass through these edges in order to reach the sink, the amount of material that can reach the sink is also limited by the sum of the capacities of these edges. This "division" of the network therefore provides an upper bound on the amount of total material that can flow through the network. The idea will be to find divisions (which we will call cuts) with smaller and smaller total capacities, since this will shrink the range of possible flow values that are attainable in the network.

Therefore, every possible flow in a network has a value that is at most the total capacity of every cut in the network. We'll further see that the flow produced by the Ford-Fulkerson algorithm has the same value as some cut. Since no flow have value bigger than a cut, this means that the Ford-Fulkerson flow must be the largest possible flow.

We start by making a more precise definition of a cut in a network. An s-t cut in a network N is a partition of the vertices into two sets, A and B, such that the source s is in the set A and the sink t is in the set B. Note that the vertices within one side of the partition need not be connected to each other.

We observe that if f is a flow in N and (A,B) is an s-t cut, then the value of f is the flow out of A minus the flow into A, or equivalently, the flow into B minus the flow out of B. The proof comes from the conservation of flow: for every edge where both vertices are in A, the flow 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.

From this notion of a cut, it is natural to ask, "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 the sum of the capacities of edges crossing over from A into B. The capacity of a cut represents an upper bound on the amount of flow that can go from s to t. The proof of this statement goes like this:

The value of the flow is the flow out of the set A minus the flow into the set A. This is less than or equal to the flow out of A, which is bounded by the sum of the capacities of the edges from A to B: this sum is then the capacity of the cut. Note from this proof that the inequality will be tight when there is no flow moving back into A and all the crossing edges are saturated: that is, the flow is equal to the capacity. Keep this in mind.

We are now ready for the big theorem of this lesson, the Max-Flow Min-Cut Theorem:

Let N be a network. The following statements are equivalent:

(1) f is a maximum flow in N.

(2) The residual network Nf has no path from s to t (i.e. no augmenting paths).

(3) There is an s-t cut in N such that the capacity of the cut equals the value of f.

As an immediate corollary, the Ford-Fulkerson algorithm produces a maximum flow. Let's look at the proof of the theorem.

We start by showing that if f is a maximum flow in the network N, then the residual network has no augmenting paths. The proof is by contradiction: suppose not, and let f' be an augmenting flow. Then we can augment f by f' and the value of the sum will be the sum of the values. The value of the augmenting flow is positive, so we have created a new flow with greater value, contradicting the the assumption that f was a maximum flow.

Next, we show that if f is a flow such that the residual network Nf has no augmenting paths, then 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 reachable from the source s in the residual network, and let B be all the other vertices. If (u,v) is a crossing edge from A to B, what does that implies about the flow, then u is reachable from the source but v is not, so the edge (u,v) is not in the residual graph. Thus, (u,v) is saturated: the flow across the edge equals its capacity. On the other hand, if (u,v) is a crossing edge from B to A, then there can't be any flow across the edge, or else the antiparallel edge (v,u) would be in the residual network (by the way we constructed the residual network), which is again impossible because A and B are separated in the residual network.

Recall that for every cut, the value of a flow is equal to the flow out of A minus the flow into the A. As we've just argued, there is no flow back into A, and the flow out of A saturates all A-B edges. Therefore, the value of the flow equals the sum of the capacities across the cut. That completes that part of the theorem.

Lastly, we need to show that the existence of a cut whose capacity equals a flow's value implies that the flow is maximum. This follows immediately from our earlier argument that the cut capacity is an upper bound on the max flow. This completes the theorem.

The max-flow min-cut theorem is a classic theorem in the study of algorithms and is also a wonderful illustration of duality, which we'll discuss in a later lesson.

So far, we've addressed our first lingering question about the Ford-Fulkerson algorithm: we've determined it does produce a maximum flow in a network. Now we turn to our second lingering question: its 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 at least one.

Indeed, this bound is tight. Consider the following network:

The answer is the worst possible, 200. This means that the bound we had before on Ford-Fulkerson is tight. It can take as many iterations are there are units in the maximum flow.

However, to obtain this many steps, we have to make poor choices for picking which augmenting paths to use: we have to choose the longest path in each situation. Two ideas for picking better paths are to prefer paths with more capacity and to prefer shorter paths.

One idea to speed up the running time of the algorithm is to find the heaviest possible flow. We could do this by starting with an empty network, and then adding the edge with the largest remaining residual capacity until there is an s-t path. However, this would be unnecessarily slow. Instead, let's try the following strategy.

Start by defining the residual network with threshold Δ, denoted Nf(Δ) to be the residual network obtained by keeping only those edges whose residual capacity exceed Δ. (Note that when Δ = 1, this is equivalent to the traditional residual network.)

  • Initialize a flow f on N so that f(u,v) = 0 for all vertices u,v.

  • Compute the residual network Nf.

  • Initialize the parameter Δ to be the sum of the capacities of all edges in N coming out from the source. (This is a trivial upper bound on the residual capacity for any edge.)

  • While Δ ≥ 1:

    • While there exists an augmenting path P in Nf(Δ):

      • Augment the flow f in N along P.

      • Update the capacities of the edges in Nf.

    • Set Δ = floor(Δ/2).

We can analyze some of this algorithm by inspection. Letting C be the initial value for Δ, we need O(log C) iterations of the outer loop, and each iteration of the inner loop costs only O(|E|) time. We are left to determine how many times we need to iterate the inner loop.

The key claim is that, for a given Δ, the maximum number of iterations of the inner loop is at most twice the number of edges in the graph. To show this, we prove the following lemma:

If Nf(Δ) has no s-t path, then there is an s-t cut (A,B) such that C(A,B)v(f) + |E|(Δ-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 Nf(Δ), and let B be remaining vertices of the residual network. Edges from A to B in this graph must have residual capacity at most Δ-1, and edges from B to A can't have flow more than Δ-1 or else the reverse edge would also appear in the graph.

The value of the flow equals the flow out of A minus the flow into A. With these bounds, we can argue that this is at least the capacity of the cut minus the number of edges in the graph times (Δ - 1). This ends the proof of the lemma.

Now we prove the main claim, that the maximum number of iterations of the inner loop of the algorithm is at most 2|E|.

The base case where Δ = C is trivial: here there can be only one iteration.

For subsequent iterations, we let f be the flow after the completing the inner loop for Δ = d, and let g be the flow before, which would have been obtained after completing the inner loop with Δ = 2 d or 2 d + 1.

The flow f is at most the maximum flow, but this is at most the capacity of the s-t cut induced by the residual network from the previous iteration. The lemma says that this is at most the value of the flow g plus the number of edges times 2 d.

Now let k be the number of iterations of the inner loop needed to augment from g to f. Each iteration increased the flow by at least Δ, so k Δ is a lower bound for the difference between the values of f and g, but as we've seen this is bounded above by 2|E|Δ, so k ≤ 2|E|.

This completes the analysis of the scaling algorithm. We have at most O(log C) iterations of the outer loop and O(|E|) iterations of the inner loop with each iteration costing O(|E|) time. The total is therefore O(|E|2 log C).

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.

  • Initialize a flow f on N so that f(u,v) = 0 for all vertices u,v.

  • Compute the residual network Nf.

  • While there exists an augmenting path in Nf:

    • Find the shortest such augmenting path P.

    • Let b be the minimum capacity over all edges (u, v) in P.

    • Augment the flow f in N by b along the path P.

    • Update the capacities of the edges in Nf.

The cost of an iteration of the while-loop is O(|E|), as we can use breadth-first search to find the shortest s-t path in the residual network. We'll show that the number of iterations of this loop is O(|V||E|), showing that Edmonds-Karp returns a maximum flow in O(|E|2|V|) time.

We'll sketch the analysis of the number of iterations. To do this, we define something called a level graph. The level of a vertex v in a graph G is defined to be the length of the shortest path from the source vertex s to v. The level graph of G is then a subgraph of G that includes only those edges connecting vertices from some level h to level h + 1 (that is, only edges that go between vertices whose levels differ by exactly 1).

The first observation we make is that augmenting along a shortest path P in the residual network never creates a path that is shorter than P. (Add link to video for explanation of this point). Next, we observe that the shortest path distance must increase every |E| iterations. Every time we use an augmenting path, we delete an edge from the level graph: the edge that got saturated by the flow. These edges won't come back into the level graph until the minimum path length is increased. Finally, there are at most |V| possible shortest path lengths, so that completes the theorem.

Notice that we've eliminated the dependence of the running time on the capacities. This means that the algorithm is now strongly polynomial, which means we can eliminate the requirement that the capacities be integers entirely.

There is one more refinement to the algorithm that is due to Dinic. He actually published his algorithm in 1970, two years before Edmonds and Karp published their result. Dinic's 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.

The algorithm proceeds as follows:

  • Initialize a flow f on N so that f(u,v) = 0 for all vertices u,v.

  • Compute the residual network Nf.

  • While there exists an augmenting path in Nf:

    • Find the shortest such augmenting path P, and let k be its length.

    • While there exists an augmenting path of length k:

      • Let b be the minimum capacity over all edges (u, v) in P.

      • Augment the flow f in N by b along the path P.

      • Update the capacities of the edges in Nf.

When there are no more augmenting paths, we return the flow f.

Turning to the analysis, we'll call one iteration of the outer while-loop a phase. We'll be able to argue that each phases 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's flow doesn't create a shorter augmenting path. Hence, once we have exhausted all paths of a given length, the next shortest path must be one edge longer.  Thus, there are at most O(|V|) phases.

We turn to the key part of the analysis where we show that each phase takes O(|V| |E|) 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 a breadth-first search, which takes O(|E|) time, and saving all forward edges while ignoring backwards and lateral ones.

When we augment the flow along a path, we introduce reverse edges into the residual graph. 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. If these new edges are useless, there is no need to rebuild the level graph of G_f when the old one will serve just as well. Therefore, Dinic's algorithm just updates the residual capacities.

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. There are only |V| vertices in the graph, so we can't run into more than |V| dead-ends. Moreover, every augmentation deletes the bottleneck edge, and we can't delete more than |E| edges. Overall, we won't try more than |E| paths.

The process of building these paths and augmenting flows is proportional to the path length, making the overall time cost of a phase O(|V| |E|).

Taking this altogether, we have |V| phases each costing us O(|VE|) time, giving us a total of O(|V|2 |E|) time, and improvement over the O(|V| |E|2) running time of the Edmonds-Karp algorithm.


Bipartite Matching


Linear Programming


Duality