Disconnecting set in the maximal flow problem

Question

I was going through a theorem presented in Ford and Fulkerson's famous paper on the maximum flow problem. Even though the theorem is intuitive, there is a step stated in the proof that I could not quite follow.

(Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian journal of Mathematics, 8, 399-404)

$\textbf{Disconnecting set:}$ A disconnecting set is a collection of arcs that has the property that every chain (i.e., path) joining the source and sink meets the collection.

Let $S$ be the class of all arcs that are saturated in every maximal flow.

$\textbf{Theorem:}$ S is a disconnecting set.

$\textbf{Proof.}$ Suppose for contradiction, S is not a disconnecting set. Then, there exists a path containing the following arcs $a_1,a_2, \cdots, a_3$ which joins the source and the sink with $a_i \notin S, \forall i$. Hence, corresponding to each $a_i$ there is a maximal flow $f_i$ in which $a_i$ is unsaturated. But the average of these flows

$\begin{equation} f= \frac{1}{m} \sum_{i=1}^{m} f_i \end{equation}$

is maximal and $a_i$ is unsaturated by $f$ for each $i$.

I did not understand the argument of the average flow. Can someone explain to me how $f_i$ is maximal and how the average over maximal flows across the path is used?

Answer 1

Let's first recall what a flow is. Given a directed graph $G = (V,E)$ and a capacity function $c : E \to \mathbb{R}_+$, and two distinct vertices $s$ and $t$ (the source and the sink), a flow is a vector $f \in \mathbb{R}^E$ satisfying the constraints: $$ \begin{align*} \textrm{excess}_f(u) = 0 &\quad (\forall u \in V \setminus \{s,t\})\\ 0 \leq f(e) \leq c(e) &\quad (\forall e \in E) \end{align*} $$ These are the law of conservation and the capacity constraints.

Here $\textrm{excess}_f(u) := \sum_{e \in \delta^+(u)} f(e) - \sum_{e \in \delta^-(u)} f(e)$ is the amount of flow that accumulates at vertex $u$. Finally the value $|f|$ of the flow $f$ is $|f| := \textrm{excess}_f(t)$.

Let $a_1,a_2,\ldots a_k$ be the arcs of the path $P$ from $s$ to $t$ such that none of these arcs is in $S$. That is, for any $i \in [1,k]$, there is a maximal flow $f_i$ that do not saturate $a_i$. Thus we have $f(a_i) < c(a_i)$. By maximality, $|f_1| = |f_2| = \ldots = |f_k|$ is the maximal flow value.

The average of several flows from $s$ to $t$ is itself a flow from $s$ to $t$. Let's check it,we define $f := \frac{1}{k} \sum_{i=1}^k f_i$.

Firstly $f$ satisfies the law of conservation: indeed let $u \in V \setminus \{s,t\}$, we have:

$$ \begin{align*} \textrm{excess}_f(u) &= \sum_{e \in \delta^+(u)} f(e) - \sum_{e \in \delta^-(u)} f(e) \\ &= \sum_{e \in \delta^+(u)} \left(\frac{1}{k} \sum_{i=1}^k f_i(e) \right) - \sum_{e \in \delta^-(u)} \left(\frac{1}{k} \sum_{i=1}^k f_i(e) \right) \\ &= \frac{1}{k} \sum_{i=1}^k \left( \sum_{e \in \delta^+(u)} f_i(e) - \sum_{e \in \delta^-(u)} f_i(e) \right) \\ &= \frac{1}{k} \sum_{i=1}^{k} \textrm{excess}_{f_i}(u) \\ &= 0\end{align*} $$

Secondly $f$ satisfies the capacity constraints: indeed let $e \in E$ an arbitrary arc, we have:

$$0 \leq f(e) = \frac{1}{k} \sum_{i=1}^k f_i(e) \leq \frac{1}{k} \sum_{i=1}^{k} c(e) = c(e)$$.

Also the value of the average flow is the average of the values of each flow, in our case it is the maximal flow value.

$$|f| = \textrm{excess}_f(v) = \frac{1}{k} \sum_{i=1}^k \textrm{excess}_{f_i}(v) = \frac{1}{k} \sum_{i=1}^k |f_i| = |f_1|$$

Hence $f$ has the same flow value as any maximal flow, $f$ is itself maximal.

Now let's see what happens for one of our arcs $a_j$, for $j \in [1,k]$. If we rewrite the inequations for the capacity constraints, we get:

$$0 \leq f(a_j) = \frac{1}{k} \sum_{i=1}^k f_i(a_j) < \frac{1}{k} \sum_{i=1}^{k} c(a_j) = c(a_j)$$.

Notice the strict inequality: this is because $f_i(a_i) < c(a_i)$ by definition of $f_i$.

Hence $f$ is maximal, but none of the arcs $a_1,\ldots a_k$ is saturated. But those arcs are the arc set of a path $P$ from $s$ to $t$, which means that $P$ is an augmenting path for $f$. This contradicts the maximality of $f$.

Actually most of this argument comes from the fact that the constraints are linear inequalities, whose intersection must be a convex polyhedron. The convexity explains why the average of several flows is a flow. The flow $f$ that we build as an average of the $f_i$'s is built to be "in the interior" of the polyhedron, and thus not be maximal.