Formulations of Max Flow

Posted: 2020-08-01.

There are a couple ways to teach max flow and the Ford-Fullkerson algorithmic framework. While the high-level ideas are similar, the differences can be confusing if you haven't seen both. They're also interesting from a philosophical, pedagogical, and practical perspective! This post briefly reviews the approaches along with a variant of my own.

Sources include:

• The "CLRS" Introduction to Algorithms textbook, 3rd edition (a note suggests that the second edition was somewhat different, perhaps closer to Kozen).
• Kleinberg and Tardos' Algorithm Design textbook.
• Jeff Erickson's Algorithms textbook.
• Kozen's The Design and Analysis of Algorithms textbook.
• Bobby Kleinberg's lecture notes.

To Net, or Not

Recall that a flow $f$ in a directed graph models some amount of e.g. water or traffic moving along edges of the graph from a source $s$ to a sink $t$. The two constraints on a flow are (1) each intermediate vertex has net flow zero, i.e. "flow in = flow out"; and (2) flow along any edge $e$ is at most the capacity $c(e)$ of that edge.

Now, the key distinction between different formalizations is whether the function $f$ represents:

1. A nonnegative flow along each edge of the original graph, OR
2. The net flow, positive or negative, between pairs of vertices of the original graph.

Most treatments I can find take the first approach, which is more intuitive. However, it causes problems with "anti-parallel edges", i.e. cases where $(u,v)$ and $(v,u)$ are both in the graph and flow can go either (or both?) directions. The resulting solutions may be viewed as inelegant, and if implemented literally could add some inefficiencies.

In contrast, Kozen (apparently much less popular, though some lecture notes follow it) takes the second approach, leading to a very elegant and implementation-friendly presentation.

Kleinberg's lecture notes on max flow/min cut interestingly take the first approach philosophically, but elegantly use multi-graphs to avoid some of the problems. However, while the result is mathematically appealing, it is not algorithm- or implementation-friendly.

After reviewing each of these, I'll describe an variant that keeps some of the advantages of Kozen while philosophically falling into the first camp.

Forward Flow

Recall we are given a directed graph $G = (V,E)$ and a capacity function $c: E \to \mathbb{R}_{\geq 0}$. We extend $c$ to a function on all pairs of vertices by letting $c(u,v) = 0$ if $(u,v) \not\in E$.

The most natural approach to network flow is to define $f: E \to \mathbb{R}_{\geq 0}$, a function that gives the amount of nonnegative flow along each edge $e \in E$. Again, it is convenient for notation to define $f(u,v) = 0$ for $(u,v) \not\in E$. The constraints on $f$ are:

• (capacity) for all $e \in E$, we have $f(u,v) \leq c(u,v)$.
• (flow) for all $u \not\in \{s,t\}$, we have $\sum_v f(u,v) = \sum_v f(v,u)$.

In particular, the second says that the net flow out of $u$ equals the net flow in.

The next step is to define the residual capacity $r$, which captures how much more flow can be sent along an edge $e = (u,v)$. Naturally, the residual capacity is $r(u,v) = c(u,v) - f(u,v)$. But a key to max flow algorithms is that one can also decrease $f$ to zero, and this is modeled by "sending" flow in the reverse direction. So for an edge $(u,v)$, the residual capacity in the opposite direction is $r(v,u) = f(u,v)$.

Now we see the problem: if there is an "anti-parallel" edge $(v,u)$ in the graph as well, then we have conflicting definitions for the residual capacities $r(u,v)$ and $r(v,u)$.

The textbook solution, appearing e.g. in CLRS, Kleinberg and Tardos, and Erickson, is to simply assume there are no anti-parallel edges in the graph: either $(u,v)$ or $(v,u)$ can be present, but not both. (There are often additional assumptions: $s$ has no incoming edges, $t$ no outgoing edges; all vertices are reachable from $s$ and can reach $t$.)

One justification for this ugly assumption is as follows: given a general directed graph $G$, one can use a reduction to construct a new $G'$ that has no antiparallel edges; then the solution to max flow on $G'$ is used to compute the solution for $G$. Pedogogically, this is actually great for giving students practice thinking about graph reductions. But, it's not pretty or elegant. And constructing an entirely new graph (possibly doubling the number of edges and/or vertices) doesn't sound very efficient in practice either.

Philosophically, one can see a tension in that while $c$ and $f$ are defined on edges, $r$ is really a relationship between pairs of vertices representing net residual capacity.

Nothing But Net

In contrast, let's review the approach found in e.g. Kozen's textbook.

Here, $f(u,v)$ represents net flow between vertices $u$ and $v$. Hence $f$ is defined for all pairs $(u,v) \in V \times V$, although for implementation efficiency, it is not necessary to write it all down as $f(u,v)$ will be zero if there are no edges between $u$ and $v$.

Now, there are three constraints:

• (capacity, same as above) for all $e \in E$, we have $f(u,v) \leq c(u,v)$.
• (flow) for all $u \not\in \{s,t\}$, we have $\sum_v f(u,v) = 0$.
• (skew-symmetry) for all $u,v$, we have $f(u,v) = -f(v,u)$.

The flow constraint now says that the net flow out of $u$ must be zero; and we have added the final constraint that the net flow from $u$ to $v$ is the inverse of the net flow from $v$ to $u$.

In this case, we need no assumptions at all on the graph structure, and can simply define $r(u,v) = c(u,v) - f(u,v)$, the amount of additional net flow one can send from vertex $u$ to $v$. Notice that this is meaningful and correct even if $f(u,v)$ is negative.

The Ford-Fulkerson framework now becomes direct and efficient:

1. Initialize $f(u,v) = 0$ for all $u,v$.
2. Find a path from $s$ to $t$ using only edges where $r(u,v) > 0$; notice there is no need to "compute" the residual graph in advance, as one can calculate $r(u,v)$ in constant time simply by querying $c$ and $f$.
3. Augment $f$ along this path by calculating $\alpha = \min_{u,v} r(u,v)$ over all consecutive pairs $u,v$ in the path, and setting $f(u,v) += \alpha$ for each such pair (adjusting $f(v,u)$ to match).
4. Repeat steps 2 and 3 until no path can be found.

As you can tell, I like the simplicity of this approach (and I plan to teach it). However, I am sympathetic to arguments that we should, philosophically, model flow rather than net flow. Indeed, the only reason the Kozen approach works is that even if antiparallel edges $(u,v)$ and $(v,u)$ are present, a maximum flow can always be found that is zero along one of the edges and nonnegative along the other. But this approach cannot distinguish e.g. a pair of opposite flows of value $1$ and $3$ from a pair of value of $0$ and $2$.

Multi-Graphs

Motivated by this philosophical objection, R. Kleinberg in his lecture notes presents a way to model positive flows along edges (rather than net flows), without making inelegant assumptions about antiparallel edges.

To do so, he considers multi-graphs in which there can be parallel edges, i.e. multiple edges between a given pair of vertices. To create the residual graph, for each $e = (u,v) \in E$ he adds both an edge $e$ and a corresponding reverse edge $\bar{e} = (v,u)$. Now the residual capacity along $e$ is $r(e) = f(e) - c(e)$, while the residual capacity along $\bar{e}$ is $r(\bar{e}) = f(e)$.

Notice that if there are antiparallel edges $(u,v)$ and $(v,u)$ in the original graph, then the residual graph is now a multi-graph: it has two edges in each direction between $u$ and $v$. Now, it turns out, the first approach to max flow simply works, without needing any assumptions on the input graph! One simply has to remember to sum over all edges.

This is a nice alternative take, especially for the mathematical lemmas and theorems proven in those notes. But the notes are more focused on interesting consequences of the max-flow min-cut theorem than on algorithms such as Ford-Fulkerson. Direct implementations would also suffer from efficiency issues compared to the previous approach.

A compromise

It turns out that with only a small tweak, one can combine some of the strengths of the two approaches. I haven't seen this written down anywhere, so hopefully you find it interesting!

We define $f$ to be the nonnegative flow along an edge of the original graph, just as in approach (1), with the same capacity and flow constraints. The only difference is in a slightly more complicated definition of residual capacity: for all $u,v$, define

That is: the amount of flow we can send from $u$ to $v$ is the amount we can decrease in the reverse direction, plus the residual capacity in the forward direction.

In the case of antiparallel edges, this approach simply sums the two contributions that one would get in approach (1).

The modifications to the description of the algorithm are small, though the augmentation step is a bit ad-hoc. Notice that $r(u,v) \geq 0$ as $f(v,u) \geq 0$ and $c(u,v) \geq f(u,v)$. The algorithm is:

1. Initialize $f(u,v) = 0$ for all $u,v$.
2. Find a path from $s$ to $t$ using only edges where $r(u,v) > 0$ (again there is no need to "compute" $r$ in advance).
3. Augment $f$ along this path as follows: Calculate $\alpha = \min_{u,v} r(u,v)$ over all consecutive pairs $u,v$ in the path. Then for each such $u,v$, first attempt to decrease the reverse flow $f(v,u)$ by $\alpha$; then if there is some amount $\alpha'$ left over, increase $f(u,v)$ by $\alpha'$.
4. Repeat steps 2 and 3 until no path can be found.

The advantage of this approach is that it is almost as simple and efficient as approach (2), yet it philosophically respects the perspective that $f$ tracks flow rather than net flow. In terms of implementations, it may be useful if nonnegative flows are already assumed by the context for some reason, and possibly-negative net flows wouldn't be allowed. However, the augmentation routine adds some annoying constant-time steps. In terms of pedagogy, it may or may not be preferable to teach compared to approach (1). But I plan to stick to teaching approach (2) for now.