Residual Graph in Maximum Flow

Question

I am reading about the Maximum Flow Problem here. I could not understand the intuition behind the Residual Graph. Why are we considering back edges while calculating the flow?

Can anyone help me understand the concept of Residual Graph?

How does the Algorithm change in Undirected Graphs?

Answer 1

The intuition behing the residual graph in the Maximum flow problem is very well presented in this lecture. The explanation goes as follows.

Suppose that we are trying to solve the maximum flow problem for the following network $G$ (where each label $f_e/c_e$ denotes both the flow $f_e$ pushed through an edge $e$ and the capacity $c_e$ of this edge):

One possible greedy approach is the following:

1. Pick an arbitrary augmenting path $P$ that goes from the source vertex $s$ to the sink vertex $t$ such that $\forall e \: (e \in P \rightarrow f_e \lt c_e $); that is, all of the edges in $P$ have available capacity.
2. Push the maximum possible flow $\Delta$ through this path. The value of $\Delta$ is determined by the bottleneck of $P$; that is, the edge with minimum available capacity. Formally, $\Delta=\min_{e \in P} (c_e-f_e)$.
3. Go to step 1 until no augmenting paths exist.

That is, find a path with available capacity, send flow along that path, and repeat.

In $G$, one possible execution of the above heuristic finds three augmenting paths $P_1$, $P_2$, and $P_3$, in this order. These paths push 2, 2, and 1 units of flow, respectively, for a total flow of 5:

Choosing paths in this order leads to an optimal solution; however, what happens if we select $P_3$ first (i.e., before $P_1$ and $P_2$)?

We get what is called a blocking flow: no more augmenting paths exist. In this case, the total flow is 3, which is not optimal. This issue can be resolved by allowing undo operations (i.e., by allowing flow to be sent in reverse, undoing work of previous iterations): simply push 2 units of flow backwards from vertex $w$ to vertex $v$ like this:

Encoding these allowed undo operations is the main goal of the residual graph.

A residual graph $R$ of a network $G$ has the same set of vertices as $G$ and includes, for each edge $e=(u,v) \in G$:

• A forward edge $e'=(u,v)$ with capacity $c_e-f_e$, if $c_e-f_e \gt 0$.

• A backward edge $e''=(v,u)$ with capacity $f_e$, if $f_e \gt 0$.

For example, consider the residual graph $R$ that is obtained after the first iteration of the greedy heuristic when the heuristic selects $P_3$ first (that is, when it gets the blocking flow):

Note that the undo operation that pushes 2 units of flow from $w$ to $v$ is encoded as a forward (augmenting) path from $s$ to $t$ in $R$:

In general:

When an augmenting path $P'$ is selected in the residual graph $R$:

• Every edge in $P'$ that corresponds to a forward edge in $G$ increases the flow by using an edge with available capacity.
• Every edge in $P'$ that corresponds to an edge going backwards in $G$ undoes flow that was pushed in the forward direction in the past.

This is the main idea behind the Ford–Fulkerson method.

The Ford–Fulkerson method proceeds in exactly the same way as the greedy approach described above, but it only stops when there are no more augmenting paths in the residual graph (not in the original network). The method is correct (i.e., it always computes a maximum flow) because the residual graph establishes the following optimality condition:

Given a network $G$, a flow $f$ is maximum in $G$ if there is no $s-t$ path in the residual graph.

Answer 2

The intuition behind the residual network is that it allows us to "cancel" an already assigned flow i.e. if we have already assigned 2 units of flow from $A$ to $B$, then passing 1 unit of flow from $B$ to $A$ is interpreted as cancelling one unit of the original flow from $A$ to $B$.