We will now examine a class of problems related to the idea of network flow. This seems a bit specific compared to the broader techniques that we've been looking at, but the interesting thing about all of these problems is that we can't actually solve them using any of our prior techniques. Rather, they operate under a principle of starting with a simple and not necessarily optimal solution, and iteratively refine and improve that solution until it is optimal.
All of the problems we'll see are based on the idea of flow through a graph.
A flow network is a tuple $G = (V,E,s,t,c)$, where $(V,E)$ is a digraph with a source $s \in v$ and a sink $t \in V$ and every edge $e \in E$ has a capacity $c(e) \geq 0$.
To simplify things, we make the following assumptions.
Here, we have a flow network with edges labelled with their capacities.
Intuitively, we want to consider the flow of some material through our graph from $s$ to $t$. Here, material is abstract, but can represent things like traffic or liquid. Let's formally define what flow is.
An $s,t$-flow is a function $f:E \to \mathbb N$ that satisfies
We say that the value of a flow $f$ is \[v(f) = \sum\limits_{e = (s,v) \in E} f(e).\]
Here, we have our network, with flow applied as labelled.
One thing to note here is that this is clearly not the most "stuff" that we can put through this network. This leads us to our problem.
The maximum flow problem is: Given a flow network $G = (V,E,s,t,c)$, find a flow $f$ of maximum value.
A seemingly natural approach for this is to use a greedy algorithm: just look at the edges with the largest capacities and measure the flow travelling on those edges. Then if we have any leftover flow, we can redirect it appropriately across the rest of the network.
Here, we have our working example after applying a "greedy" strategy of finding the largest path to saturate our flow.
We first send 8 flow through path 1 and the remaining 2 through path 2. We then try to send as much as we can through path 3. This results in a flow of 16.
However, the following is a better flow.
The main problem with this approach is the same one that fails for a lot of attempts via greedy algorithms: sometimes the greedy choice isn't the best choice and we have to go back and make some change.
If we think about how liquids or impatient drivers behave, they don't just give up when they are blocked at some point while there's still some unused capacity available. They will naturally redistribute and push back to where there is available capacity. So we need some way of formalizing this behaviour of redirecting flow.
The residual graph $G_f = (V,E_f)$ for a flow network $G$ and flow $f$ is defined for each edge $e = (u,v) \in E$,
Then the edge set $E_f$ of the residual graph $G_f$ is defined \[E_f = \{e = (u,v) \mid f(e) \lt c(e)\} \cup \{e' = (v,u) \mid f(e) \gt 0\},\] with capacity function $c_f$ defined as above, \[c(u,v) = \begin{cases} c(u,v) - f(u,v) & \text{if $(u,v) \in E$,} \\ f(u,v) & \text{if $(v,u) \in E$,} \\ 0 & \text{otherwise.} \end{cases}\]
Informally, the residual graph with respect to a particular flow $f$ gives us the capacity of the edges to get pushed backwards. If we push a particular amount of flow through our network through certain edges, how does the rest of the network absorb the flow if there isn't enough capacity? We call the capacity $c_f$ of the residual graph $G_f$ the residual capacity.
Here, we have a residual graph derived from the flow of Example 7.4.
So how do we make use of this information? Because the residual graph tells us where there is unused capacity in our flow network, we can use it to find a way to redirect the flow for a given path.
An augmenting path is a path in the residual graph $G_f$. We say the bottleneck capacity $\beta(P,f)$ of an augmenting path $P$ with respect to the flow $f$ is the minimum residual capacity of any edge in $P$.
What we would like to do is take a path that's been bottlenecked and figure out how the excess flow gets redirected. We call this process augmentation, because it results in determining an augmenting path.
The augmented flow $\alpha(f,P)$ is a flow in $G$, defined for each edge $(u,v) \in E_f$ by \[ \alpha(f,P)(u,v) = \begin{cases} f(u,v) + \beta(P,f) & \text{if $(u,v) \in P$ and $(u,v) \in E$,} \\ f(u,v) - \beta(P,f) & \text{if $(u,v) \in P$ and $(v,u) \in E$,} \\ f(u,v) & \text{if $(u,v) \not \in P$.} \end{cases} \]
Here, we augment our flow based on the residual graph of Example 7.8. We choose the following augmented path.
Then applying our augmentation with respect to this path, we see that the bottleneck is 2 and adjust our flow accordingly.
Based on our augmenting path, we get a new flow. Of course, we don't know that this is a flow; we have to show that it obeys our conservation and capacity conditions.
The augmented flow $\alpha(f,P)$ is a flow in $G$.
First, we will show that the capacity condition is preserved. We note that the only edges for which the flow has changed is on edges of $P$, so let $(u,v) \in P$. Either $(u,v)$ is a forward or a backward edge.
If $(u,v)$ is a forward edge, we observe that we increase the flow of each forward edge by $\beta(P,f)$, which was the defined to be the minimum residual capacity of any edge in $P$. Then \[0 \leq f(u,v) \leq \alpha(f,P)(u,v) = f(u,v) + \beta(P,f) \leq f(u,v) + (c(u,v) - f(u,v)) = c(u,v).\]
If $(u,v)$ is a backwards edge, we observe that we decrease the flow of each backward edge by $\beta(P,f)$. This gives us \[c(u,v) \geq f(u,v) \geq \alpha(f,P)(u,v) = f(u,v) - \beta(P,f) \geq f(u,v) - f(u,v) = 0.\] Therefore, in either case the capacity condition holds.
Then, we must show that the conservation condition holds for each vertex in our path except for $s,t$. This is done by considering the each combination of forward or backwards edges entering and exiting. We will do one case and leave the rest for you to think through.
Suppose that for our vertex $v$, we have a forward edge $(u,v)$ entering it and a backwards edge $(v,w)$ leaving it. According to $\alpha(f,P)$, we have \begin{align*} \alpha(f,P)(u,v) &= f(u,v) + \beta(P,f) \\ \alpha(f,P)(w,v) &= f(w,v) - \beta(P,f) \end{align*} Since $(v,w)$ is a backwards edge in $G_f$, its corresponding edge in $G$ is $(w,v)$, so both $(u,v)$ and $(w,v)$ enter $v$ in $G$. Then $\alpha(f,P)$ increases the amount of flow entering $v$ by $\beta(P,f)$ on $(u,v)$ but decreases the flow entering $v$ by $\beta(P,f)$ on $(w,v)$. Since $f$ preserved conservation, we can conclude $\alpha(f,P)$ preserves conservation.
But what can we say about the new flow? As it turns out, the new flow is going to be strictly greater than our previous flow.
Let $f$ be a flow in $G$ and let $P$ be a simple $s,t$-path in the residual graph $G_f$. Then $v(f') = v(f) + \beta(P,f)$. Since $\beta(P,f) \gt 0$, we have $v(f') \gt v(f)$.
Let $e$ be the first edge of $P$. Then $e$ must leave $s$ and since we are considering only simple paths, $s$ does not get revisited. Since $G$ does not contain any edges that enter $s$, $e$ must be a forward edge. When we augment $f$ on $P$, we increase the flow on $e$ by $\beta(P,f)$ and no other edge leaving $s$. Therefore, the value of $f'$ is greater than the value of $f$ by $\beta(P,f)$.
This leads us to the basic idea of the Ford-Fulkerson algorithm. Since augmenting our flows increases the flow in $G$, we can start with 0 flow and repeatedly compute augmenting flows. We stop once we are unable to do so.
\begin{algorithmic}
\PROCEDURE{max-flow}{$G = (V,E,s,t,c)$}
\FORALL{$e \in E$}
\STATE $f(e) \gets 0$
\ENDFOR
\STATE $G_f \gets$ residual graph of $G$ and $f$
\WHILE{there is an $s,t$-path $P$ in $G_f$}
\STATE $f = \alpha(f,P)$
\STATE $G_f \gets$ residual graph of $G$ and $f$
\ENDWHILE
\RETURN{$f$}
\ENDPROCEDURE
\end{algorithmic}
The Ford-Fulkerson algorithm is due to Ford, who we were introduced to via Bellman-Ford, and Fulkerson in 1956, when they were at RAND. The actual algorithm that they give is more of the math-y proof kind. This will be important when we discuss the running time in a bit.
One thing that is unclear about this is it's not clear that this algorithm will ever terminate (the danger of while loops). What if we keep computing flows indefinitely? We already know that we will always get a flow with greater value. All that remains is to observe that every graph has a strict upper bound on the value of any flow: the capacities of the edges directly leaving the source.
Let $G = (V,E,s,t,c)$ be a flow network with $c:E \to \mathbb N$. Then the Ford-Fulkerson algorithm will terminate on $G$.
We observe that the value of any flow cannot exceed the capacity of all edges leaving the source $s$. Let $C = \sum\limits_{(s,v) \in E} f(s,v)$. By Lemma 7.12, the value of any augmented flow $\alpha(f,P)$ will be strictly larger than the flow $f$ that it augments. Therefore, at each iteration of Ford-Fulkerson, the value of the flow maintained by the algorithm increases by at least 1. Since the value of the increases with each iteration and the upper bound on the value of any flow of $G$ is $C$, we can conclude that Ford-Fulkerson will terminate after at most $C$ iterations.
Now, we can consider its running time.
Let $G = (V,E,s,t,c)$ be a flow network with $c:E \to \mathbb N$. Then the Ford-Fulkerson algorithm runs in $O(mC)$ time, where $m = |E|$ and $C = \sum\limits_{(s,v) \in E} f(s,v)$.
Let $m = |E|$ and $n = |V|$ and assume that $m \geq \frac n 2$. By Proposition 7.15, the algorithm must terminate after at most $C$ iterations. Therefore, we can consider the time required for each iteration.
Since each iteration requires $O(m)$ time, the algorithm has running time $O(mC)$ in the worst case. Then we observe that the residual graph $G_f$ has at most $2m$ edges; one forwards and one backwards for each edge of $G$. This means that constructing a residual graph can be performed in $O(m)$ time. To find an $s,t$-path, we simply do a search in $O(m+n) = O(m)$ time. Then finding the augmented flow $\alpha(f,P)$ requires $O(n)$ time, since there are at most $n-1$ edges for any path $P$.
Therefore, one iteration requires $O(m)$ time, which brings us to our total of $O(mC)$ time.
One problem with this algorithm is that it is not necessarily polynomial. A bad case of this would be a flow network with an absurdly large bound of $C$ relative to the size of the graph that updates the flow by increasing by 1 with each iteration. This has to do with the fact that there's no prescribed way to choose an augmenting path.
This goes back to the discussion of Ford and Fulkerson's presentation of the algorithm, which leaves out the how for finding the augmenting path. Without such a definition, we are free to choose the worst case. However, an actual fleshed-out efficient algorithm was given by Edmonds and Karp in 1972 and this algorithm has a running time of $O(m^2n)$.
Like other algorithms we've seen, there has been a line of work in the decades since trying to improve on this result. Some of these are discussed in other sections of Kleinberg and Tardos. Edmonds–Karp is discussed in 7.3 and Goldberg and Tarjan's 1986 "preflow push" algorithm, which runs in $O(mn \log \frac{n^2}{m})$, is discussed in 7.4.
The latest result came just last year, at FOCS 2022: Chen, Kyng, Liu, Peng, Gutenberg, and Sachdeva gave an almost linear time algorithm—$m^{1+o(1)}$ time.
It remains to show that the Ford-Fulkerson algorithm actually gives us the maximum possible flow. We know a rough upper bound on the flow: the total capacity of all edges leaving the source $s$. However, this is not the best upper bound we can get.
Recall the following definition from our discussion of minimum spanning trees.
A cut is a partition of vertices into two nonempty subsets $(S,V-S)$. The cutset of a cut $S$ is the set of edges with exactly one endpoint in $S$.
Suppose we have a cut in our flow network, with $s$ in one set of the partition and $t$ in the other. We observe that the edges in the cutset that move from the $s$ side to the $t$ side constitutes a rough bound on the amount of flow that goes from $s$ to $t$. We can formalize this notion.
An $s,t$-cut is a partition $(S,T)$ of the vertex set $V$ such that $s \in S$ and $t \in T$.
One observation that we can make in the context of flows is that a cut that divides $s$ and $t$ into two different parts of the cut means that flow will necessarily travel from one side of the cut to the other. We can try to quantify some aspects of this.
The capacity of a cut $(S,T)$ is the capacity of all edges leaving $S$, \[c(S,T) = \sum_{(u,v) \in S \times T \subseteq E} c(u,v).\]
Consider the following graph. The vertices highlighted in yellow are in the set $S$, and we consider the cut $(S,T)$. Then the capacity of this cut is the capacity of edges highlighted in cyan, $3+1+5 = 9$.
Note that the capacity of the cut is much lower than the capacity of the edges leaving the source node $s$. Intuitively, it seems like any flow is subject to the capacity of a cut. After all, all flow has to travel from one side of the cut to the other. But we can go further with this: it seems like this should be true for any cut we can define, which leads us to the following problem.
The minimum cut problem is: Given a flow network $G = (V,E,s,t,c)$, find a cut $(S,T)$ with minimum capacity.
If our intuition is correct, then finding a minimum cut will give us a possibly better upper bound on the maximum flow than the outgoing capacity of the source vertex.
Let $f$ be a flow and $(S,T)$ be a cut. Then the value of a flow is the flow leaving $S$ less the flow entering $S$, \[v(f) = \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v).\]
Since there are no edges entering $s$, we have \[v(f) = \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) = \sum_{(s,v) \in E} f(s,v).\] By conservation, we have for all $v \in V$, \[\sum_{(u,v) \in E} f(u,v) - \sum_{(v,w) \in E} f(v,w) = 0.\] Then putting the two together, we have \begin{align*} v(f) &= \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) \\ &= \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) + 0 \\ &= \sum_{v \in S} \left( \sum_{(u,v) \in E} f(u,v) - \sum_{(v,w) \in E} f(v,w)\right) \\ &= \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v). \end{align*}
Consider the following flow network with cut $(S,T)$, where vertices in $S$ are highlighted in yellow and vertices in $T$ are highlighted in green. The capacities of this network are in pink, while the flow is labeled in blue. We observe that the value of the flow is 9.
The flow leaving $S$ is circled in yellow, for a total of $2+4+9$, while the flow entering $S$ is circled in blue, which totals $6$. The difference in these flows is $2+4+9-6 = 9$, which is the value of our flow.
Of course, the in-flow of $S$ is the out-flow of $T$ and the out-flow of $S$ is the in-flow of $T$, so this lemma can be reformulated in terms of $T$. This lemma leads to the following bound.
Let $f$ be a flow and $(S,T)$ be a cut. Then $v(f) \leq c(S,T)$.
\begin{align*} v(f) &= \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v) \\ &\leq \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) \\ &\leq \sum_{u \in S, v \in T, (u,v) \in E} c(u,v) \\ &\leq c(S,T) \end{align*}
This bound confirms our intutition above, that any cut places an upper bound on the flow for a given network. This means that the minimal cut for a network will give us the best upper bound on the maximum flow through that network.
Let $f$ be a flow and $(S,T)$ be a cut. If $v(f) = c(S,T)$, then $f$ is a max flow and $(S,T)$ is a min cut.
We observe that for any flow $f'$, we have $v(f') \leq c(S,T) = v(f)$. We also have that for any cut $(S',T')$, $c(S',T') \geq v(f) = c(S,T)$.
This leads us to the statement of the Max-Flow Min-Cut theorem.
The value of a maximum flow is the capacity of a minimum cut.
We will use this to show that the Ford-Fulkerson algorithm is correct, by showing that we can compute the minimum cut from it.
Let $G = (V,E,s,t,c)$ be a flow network. Then $f$ is a maxmimum flow if and only if $G_f$ contains no augmenting paths.
We will show that the following are equivalent.
$(1) \implies (2)$ is easy: this is just Corollary 7.24.
$(2) \implies (3)$ is also fairly straightforward. Suppose $G_f$ does have an augmenting path. Then we can augment $f$ and increase the flow, so $f$ wasn't a maximum flow.
So it remains to show that $(3) \implies (1)$. We have that $f$ is a flow such that $G_f$ has no augmenting paths. Then this means that not every vertex in $G_f$ is reachable from $s$, so we let $S$ be the set of vertices reachable from $s$ in $G_f$. This naturally gives us a cut $(S,T)$, since it is clear that $t \not \in S$ (otherwise, there would be an augmenting path in $G_f$).
Now, let's consider the flow on the edges in the cutset of $(S,T)$. If $(u,v)$ is an edge in $G$ with $u \in S$ and $v \in T$. This edge is not a forward edge in $G_f$, since otherwise, $v$ would have been reachable and $v \in S$. Since $(u,v)$ is not a forward edge, this means $(u,v)$ had no unused capacity by $f$, so $f(u,v) = c(u,v)$.
Next, consider an edge $(u',v')$ in $G$ with $u' \in T$ and $v' \in S$. We claim that $f(u',v') = 0$. Suppose not. Then $(v',u')$ is a backward edge in $G_f$ and $u'$ would have been reachable by $s$, which could not be the case since $u' \in T$.
Therefore, all outgoing edges of $S$ are saturated with flow and all incoming edges of $S$ are empty. By the flow value lemma, we have \begin{align*} v(f) &= \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v) \\ &= \sum_{u \in S, v \in T, (u,v) \in E} c(u,v) - 0 \\ &= c(S,T). \end{align*}
Since the Ford-Fulkerson algorithm relies on obtaining the flow for which its residual graph contains no augmenting paths, we can conclude that the flow that the Ford-Fulkerson algorithm returns is the maximum flow. But this theorem also gives us a way to compute the minimum cut of $G$.
Let $G = (V,E,s,t,c)$ be a flow network. Given a maximum flow $f$ for $G$, we can compute a minimum $s,t$-cut in $O(m)$ time.
First, we compute the residual graph $G_f$ in $O(m)$ time. Then doing a search, we can find all vertices that are reachable from $s$ in $O(m+n) = O(m)$ time.
The Max-Flow Min-Cut theorem was a part of the Ford-Fulkerson paper. But why were they interested in maximal flows? They begin their paper with the following:
The problem discussed in this paper was formulated by T. Harris as follows:
"Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other."
This sounds innocuous and kind of boring until you remember that Ford and Fulkerson were working at RAND and you realize that the rail network referred to by Harris is the Soviet rail system and maybe they weren't necessarily as interested in maximum flows as minimum cuts.
A common theme in computer science is that problems can be deeply related in very surprising ways. Network flow seems like a very particular kind of problem: we want to know how much stuff can move through a network. However, we'll see an example of a problem that doesn't involve that idea at all, but for which our network flow algorithm can be adapted to solve.
A matching in an undirected graph $G = (V,E)$ is a subset of edges $M \subseteq E$ such that no two edges in $E$ share the same incident vertex. A vertex that is incident to an edge in a matching $M$ is matched in $M$; otherwise, it is unmatched. A maximal matching is a matching that cannot be made larger; in other words, every edge in $E \setminus M$ is incident to a vertex matched in $M$. A maximum matching is a matching with the maximum number of edges.
The following graph has a matching consisting of the edges highlighted in yellow. It is a maximal matching (no more edges can be added to the matching) and a maximum matching (it is the largest matching that this graph will admit).
As the example shows, matchings can be applied to any undirected graph, not just those that are bipartite. We will focus on matching in bipartite graphs.
An undirected graph $G = (V,E)$ is bipartite if $V$ is the disjoint union of two sets $V_1$ and $V_2$ such that all edges in $E$ connect a vertex in $V_1$ with a vertex in $V_2$. We say that $(V_1, V_2)$ is a bipartition of $V$.
We are interested in the following problem.
The bipartite matching problem is: Given an undirected graph $G = (V,E)$ with bipartition $(V_1,V_2)$, find a maximum matching $M \subseteq E$.
In other words, our problem can be thought of as some version of the following: we have two groups of "things" and we are trying to pair them up. Hence, a matching.
What we will try to do is turn our instance of the bipartite matching problem into an instance of the maximum flow problem. In other words, we will transform our graph into a flow network. In doing so, if we find a maximum flow on our flow network, then the flow corresponds to a maximum matching on our bipartite graph.
Let $G = (V,E)$ be an undirected graph with bipartition $(V_1,V_2)$. We define the flow network $G' = (V',E',s,t,c)$ by the following:
Informally, we turn all edges into directed edges from vertices in $V_1$ to vertices in $V_2$. We add a source vertex $s$ with edges from $s$ to vertices in $V_1$ and add a sink vertex $t$ and edges from vertices in $V_2$ to $t$. Finally, we set the capacities of all edges to 1.
We want to show the following.
Each matching $M$ of cardinality $k$ corresponds to an integral flow $f$ with value $k$.
The forward direction is pretty simple. let $M$ be a matching of size $k$. Consider the flow $f$ that pushes 1 unit of flow through each edge of $M$. Since each edge of $M$ is incident to exactly one vertex in $V_1$ and one vertex in $V_2$, we can easily verify that this flow obeys the capacity and conservation conditions and that $v(f) = k$.
Now consider the reverse direction, and suppose $f$ is an integer-valued flow of value $k$. Clearly, flows through edges must be either 0 or 1. We will denote by $M'$ the set of edges $e$ that have $f(e) = 1$.
We claim that $M'$ has $k$ edges. To see this, we take the cut $(S,T)$ where $S = \{s\} \cup V_1$ and $T = \{t\} \cup V_2$. Applying Lemma 7.21, we get that the flow leaving $S$ is $k$ and no flow is entering $S$. Since every edge has capacity 1, we can conclude there are $k$ edges in $M'$.
Now, to show that $M'$ is a matching, we observe that no two edges carrying flow can be incident to the same vertex, as every vertex in $V_1$ has an incoming capacity of 1 and every vertex in $V_2$ has an outgoing capacity of 1.
Then an algorithm for finding the maximum matching of a bipartite graph is clear: given a bipartite graph $G$, construct the flow network $G'$ as described in Definition 7.32 and find a maximum flow for $G'$. Is this efficient? It turns out that even in the simplest incarnation of Ford-Fulkerson, we get a feasible algorithm.
A maximum matching in a bipartite graph can be found in $O(mn)$ time.
Recall that the running time of Ford-Fulkerson was $O(mC)$, where $C$ was the upper bound on the capacity of the graph. This was potentially bad if $C$ was much larger than our graph, but here, $C = n$, which makes this perfectly fine.
One of the things about this result is that it actually gives us a way to solve bipartite matching without having to transform our graph into a flow network. First, let's suppose we have a flow $f$ in our network $G'$ that's not maximum. Then there is an augmenting path in our residual graph $G_f'$. But since all of the edges in our network have capacity 1, any augmenting path will be made up of alternating forward and backward edges. This leads to a situation like the following.
An augmentation of the flow will result in us essentially swapping edges of the augmenting path so that those that were carrying flow will no longer do so and those that were empty will have flow. In our graph, this appears as though we've swapped the edges of our matching.
If you ever happened to take discrete math with me, then you will recognize this as the algorithm I presented for bipartite matching, due to Claude Berge in 1957. The idea is very similar to the iteratively-improving solution technique used for maximum flows:
In the following example, we take the yellow edges to be our initial matching. Then, there are two possible augmenting paths, one in cyan and one in green. Flipping the edges in and out of the matching in both paths will increase the size of our matching.
Of course, now, we recognize this clearly as a special case of the Ford-Fulkerson algorithm.
A natural question is to ask whether we can pull this off with a graph that is not bipartite. The answer to that is not quite. General graphs will have an inconvenient structure that makes the algorithm less straightforward. However, there is a polynomial time algorithm for computing maximum matchings in graphs, due to Edmonds in 1965. We won't be looking at this algorithm, but Edmonds says something very interesting in this paper.
In particular, one of the claims of his paper is that this algorithm is efficient ($O(n^4)$, in fact), but remember that this is 1965, so the question of what an efficient algorithm is not quite settled. His claim is that because his algorithm increases not exponentially, but algebraically with respect to the size of the graph, it can be considered efficient. Here, algebraically of course means polynomially and he discusses the implications of this definition in Section 2.
My alma mater is the University of Waterloo, which was where Edmonds was a faculty member, in the Department of Combinatorics and Optimization, so the first time I heard about Edmonds was with respect to his matching algorithm and his discussion of efficient algorithms. The second time I heard about him was in grad school, from an officemate, who had also gone to school at Waterloo, who told me that Edmonds had a rock outside of his home that was inscribed with $NP \neq NP \cap coNP = P$. His page on Wikipedia was recently updated to include a photo of him with his rock outside his home.