5.2. Preflow-Push Algorithms

The main characteristic of augmenting path algorithms is that they maintain the invariant that the current \(st\)-flow \(f\) is feasible at any point in the algorithm. They use augmenting paths to increase the flow while maintaining feasibility. Preflow-push algorithms approach the problem from a different angle: Clearly, the maximum amount of flow that could possibly be moved from \(s\) to \(t\) is

\[\sum_{y \in V} u_{s,y},\]

the total capacity of \(s\)'s out-edges. So the algorithm is optimistic and pushes exactly \(u_{s,y}\) units of flow along every out-edge \((s,y)\) of \(s\), hoping that it will eventually be able to move all this flow to \(t\). At this point, \(s\)'s out-neighbours do not satisfy flow conservation, so the algorithm tries to re-establish flow conservation by pushing the flow each neighbour \(y\) receives from \(s\) on to its out-neighbours. If \(y\)'s out-edges have sufficient capacity, this restores flow conservation at \(y\) but now creates an excess of flow at \(y\)'s out-neighbours. By pushing flow along in this fashion, a certain amount of flow eventually reaches \(t\) while some nodes in \(G\) may still be left with an excess flow they were not able to pass on to any of their out-neighbours. This flow is sent back to \(s\) to restore flow conservation, at which point the resulting flow is feasible and, as we show below, maximum if the algorithm is implemented correctly.

The first part of the name of these algorithms stems from the following definition:

A preflow is a function \(f: E \rightarrow \mathbb{R}\) such that

\[0 \le f_e \le u_e \quad \forall e \in E\]

and

\[\sum_{y \in V} \bigl(f_{y,x} - f_{x,y}\bigr) \ge 0 \quad \forall x \in V \setminus \{ s, t \}.\]

In other words, \(f\) satisfies the capacity constraints and no vertex other than \(s\) or \(t\) generates any flow.

Every preflow-push algorithm initializes the preflow by setting

\[f_{x,y} = \begin{cases} u_{x,y} & \text{if } x = s\\ 0 & \text{if } x \ne s \end{cases}\]

for every edge \((x,y) \in G\).

The quantity

\[e_x = \sum_{y \in V} \bigl(f_{y,x} - f_{x,y}\bigr)\]

is called the excess at node \(x\). A node \(x\) is said to overflow if \(e_x > 0\).

Once every node \(x \notin \{s, t\}\) satisfies \(e_x = 0\), the current preflow is a feasible \(st\)-flow. Preflow-push algorithms turn the initial preflow into a feasible \(st\)-flow by pushing excess flow from overflowing nodes to their out-neighbours. Hence the second part of the name of these algorithms.

Preflow-push algorithms are the fastest maximum flow algorithms known today. Specifically, this section discusses three preflow-push algorithm with running times \(O\bigl(n^2m\bigr)\), \(O\bigl(n^3\bigr)\), and \(O\bigl(n^2\sqrt{m}\bigr)\). Even faster preflow-push algorithms can be obtained using efficient data structures called link-cut trees, an enhancement I decided not to discuss in this course.