7 Flows on networks, vertex and edge connectivity 7 Flows on networks, vertex and edge connectivity 7.2 Vertex and edge connectivity

7.1 Max-flow min-cut theorem

Given a simple graph $G=(V,E)$ , we set $\overleftarrow{E}$ to be the set of ordered edges of $E$ whereby we give both the orientations to an edge $e\in E$ . In other words, $e\in\overleftarrow{E}$ implies that $e=(x,y)\neq(y,x)$ and we rather denote $-e=(y,x)$ in such a case. Further, we set $e^{-}=x,e^{+}=y.$

Definition 7.1.

(Flow ) Let $s,t\in V$ (source, target). A flow $f$ from $s$ (source) to $t$ (target/sink) is a function $f:\overleftarrow{E}\to\mathbb{R}$ such that

1.

(anti-symmetry) $f(e)=-f(-e)$
2.

(Kirchoff’s node law ) $(d^{*}f)(x):=\sum_{e:e^{-}=x}f(e)=0$ for all $x\neq\{s,t\}.$
3.

(Positive output at source :) $(d^{*}f)(s)\geq 0$ .

Definition 7.2.

Let $c:E\to[0,\infty]$ be the capacity function. A flow from $s$ to $t$ is said to satisfy the capacity constraints if $f(e)\leq c(e)$ and we call such a flow feasible.

One can suitably define in-flow and out-flow at a vertex and show that Kirchoff’s node law implies that the in-flow and out-flow are equal at all vertices except the sink. We can further define value of a flow $v(f):=d^{*}f(s)$ . Using double-counting and anti-symmetry, we derive that

\sum_{x\in V}d^{*}f(x)=\sum_{e\in\overleftarrow{E}}f(e)=\frac{1}{2}\sum_{e\in% \overleftarrow{E}}\Big{(}f(e)+f(-e)\Big{)}=0.

So, from Kirchoff’s node law and definition of $v(f)$ , we obtain $-d^{*}f(t)=d^{*}f(s)=v(f)$ .

Let $S\subset V$ . We call a pair $(S,S^{c})$ a $(s,t)$ -cut if $s\in S,t\notin S$ . Defining $C(X,Y)=\sum_{x\in X,y\in Y}c(x,y)$ , $f(X,Y)=\sum_{x\in X,y\in Y}f(x,y)$ , we can show that $v(f)=f(S,S^{c})$ for any $(s,t)$ -cut $(S,S^{c})$ and any feasible $s-t$ flow. Note that if $S=\{s\}$ , $v(f)=f(S,S^{c})$ by definition. Re-iterating the above argument,

	$\displaystyle v(f)$	$\displaystyle=d^{}f(s)=\sum_{x\in S}d^{}f(x)=\sum_{e\in\overleftarrow{E},e^{% -}\in S}f(e)$
		$\displaystyle=\sum_{e,e^{-},e^{+}\in S}f(e)+\sum_{e,e^{-},e^{+}\in S}f(e)$
		$\displaystyle=\frac{1}{2}\sum_{e,e^{-},e^{+}\in S}\Big{(}f(e)+f(-e)\Big{)}+f(S% ,S^{c})=f(S,S^{c}).$

Thus, we have that $v(f)=f(S,S^{c})\leq C(S,S^{c})$ for a feasible $s-t$ flow and so

\sup\{v(f):f\,\,\mbox{is a $(s,t)$-flow}\}\leq\inf_{S:s\in S,t\notin S}C(S,S^{% c}).

That the converse holds is the non-trivial max-flow min-cut theorem that we will state and prove now. Since the infimum for cuts is taken over a finite set, it is trivally a minimum. Though the LHS may not always be a maximum (see Lemma 7.4 and Exercise 7.8), we refer to it as max-flow and the RHS as min-cut.

Theorem 7.3 (Max-flow min-cut theorem ; Elias-Feinstein-Shannon and Ford-Fulkerson (1956) ).

\sup\{v(f):f\,\,\mbox{is a feasible $(s,t)$-flow}\}=\min_{S\subset V:s\in S,t% \notin S}C(S,S^{c}).

It will soon become clear that Max-flow min-cut theorem is not a single theorem but a class of theorems that can be proven under different frameworks using variants of the ideas we will use to prove the above theorem - Theorem 7.3. We say $P=e_{1}\ldots e_{k}$ is a $s-t$ path if $e_{1}^{-}=s,e_{k}^{+}=t$ and $e_{i}^{+}=e_{i+1}^{-}$ for all $1\leq i<k$ .

Lemma 7.4.

If there exists an infinite capacity $s-t$ path (i.e. capacity of every edge on the path is infinite), then the max-flow is infinite and so is the min-cut. Else, the min-cut is finite and so is the max-flow.

Proof.

The proof of first part follows by constructing a sequence of flows with increasing strengths. We will prove the second part alone. Let there be no infinite capcity $s-t$ path. We construct a finite min-cut as follows : Choose an $s-t$ path $P_{1}$ and since it is not infinite, there exists $e_{1}$ such that $c(e_{1})<\infty$ . Now repeat this procedure on $G-e_{1}$ and choose an edge $e_{2}$ in a $s-t$ path $P_{2}$ such that $c(e_{2})<\infty$ . Repeatedly, we can choose edges $e_{1},\ldots,e_{k}$ until $G-\{e_{1},\ldots,e_{k}\}$ has no $s-t$ path. Let $S$ be the set of vertices in the component of $s$ in $G-\{e_{1},\ldots,e_{k}\}$ and clearly $t\in S^{c}$ . Since $s-t$ path exists in $G$ , we have that $E\cap(S\times S^{c})\subset\{e_{1},\ldots,e_{k}\}$ and hence $C(S,S^{c})\leq\sum_{i=1}^{k}c(e_{i})<\infty$ . ∎

Lemma 7.5.

If the capacity function is bounded, then

\sup\{v(f):f\,\,\mbox{is a feasible $(s,t)$-flow}\}=\max\{v(f):f\,\,\mbox{is a% feasible $(s,t)$-flow}\}.

Proof.

Let $f_{n}$ be a sequence of feasible $s-t$ flows such that

v(f_{n})\uparrow\sup\{v(f):f\,\,\mbox{is a feasible $(s,t)$-flow}\}.

Enumerate the set of edges in $E$ as $e_{1},\ldots,e_{m}$ . Fix an orientation for each $e_{i}$ . Since $f_{n}(e_{1})\leq c(e_{1})<\infty$ , by Bolzano-Weierstrass theorem, there exists a convergent subsequence $f_{n_{1}}(e_{1})$ such that $f_{n_{1}}(e_{1})\to x_{1}$ . Set $f_{0}(e_{1})=x_{1}$ . Now apply the argument to the sequence of flows $f_{n_{1}}$ on $e_{2}$ . This way we get a limit $x_{2}$ and set $f_{0}(e_{2})=x_{2}$ . Continuing, we get $f(e_{i})=x_{i}$ for all $1\leq i\leq m$ . This is nothing but a diagonalization argument and so we have constructed a subsequence $f_{n_{m}}$ such that $f_{n_{m}}(e_{i})\to f_{0}(e_{i})$ for all $1\leq i\leq m$ . Thus, we have that

v(f_{0})=d^{*}f_{0}(s)=\lim_{n_{m}\to\infty}d^{*}f_{n_{m}}(s)=\lim_{n_{m}\to% \infty}v(f_{n_{m}})=\sup\{v(f):f\,\,\mbox{is a feasible $(s,t)$-flow},

i.e., $f_{0}$ is the maximal element. ∎

Lemma 7.6.

Let $f$ be a $s-t$ flow in a graph and let $P=e_{1}\ldots e_{k}$ be a $s-t$ path. Then for every $\epsilon>0$ , $f^{\prime}$ defined as follows is also a flow : $f^{\prime}(e):=f(e)$ for $e,-e\neq e_{1},\ldots,e_{k}$ , $f^{\prime}(e)=f(e)+\epsilon,e=e_{1},\ldots,e_{k}$ , $f(e)=f(e)-\epsilon,e=-e_{1},\ldots,-e_{k}$ . Further $v(f^{\prime})=v(f)+\epsilon$ .

Proof.

Clearly anti-symmetry holds and $(d^{*}f^{\prime})(s)=\sum_{e:e^{-}=s}f^{\prime}(e)=\sum_{e:e^{-}=s}f(e)+% \epsilon\geq 0$ . It remains only to show that $(d^{*}f^{\prime})(v)=0$ for all $v\neq s,t$ . This holds trivially for all $v\neq e_{i}^{-},i=2,\ldots,k$ . Suppose $v=e_{i}^{-}$ for some $1<i\leq k$ . Then

	$\displaystyle(d^{*}f^{\prime})(v)$	$\displaystyle=\sum_{e:e^{-}=v}f^{\prime}(e)=\sum_{e:e^{-}=v,e\neq e_{i-1},e_{i% }}f(e)+f^{\prime}(e_{i})+f^{\prime}(-e_{i-1})$
		$\displaystyle=\sum_{e:e^{-}=v,e\neq e_{i-1},e_{i}}f(e)+f(e_{i})+f(-e_{i-1})=(d% ^{*}f)(v)=0.$

∎

We first present the Ford-Fulkerson algorithm which gives the idea of the proof.

Remark 7.7 (Ford-Fulkerson Algorithm ).

Given a flow $f$ , define the residual capacity $c_{f}(u,v)=c(u,v)-f(u,v).$

Step 1: Set $f\equiv 0$ .
Step 2 : If there is a path $P$ (called $f$ -augmenting path from $s$ to $t$ in $G$ such that $c_{f}(u,v)>0$ for all edges $(u,v)\in P$ , then go to Step 3 else go to Step 6.
Step 3 : Find $c_{f}(P)=\min\{c_{f}(u,v):(u,v)\in P\}$ (residual capacity).
Step 4 : For each edge $(u,v)\in P$ , set $f(u,v)=f(u,v)+c_{f}(P)$ and $f(v,u)=f(v,u)-c_{f}(P)$ .
Step 5 : Go back to Step 2.
Step 6 : Output flow $f$ as the maximal flow.

Defining $S_{f}$ be the set of vertices that can be reached from $s$ with a path $P$ such that $c_{f}(u,v)>0$ for all edges $(u,v)\in P$ , note that Step 2 can also be rephrased as follows : If $t\in S_{f}$ go to Step 3 else go to Step 6.

Proof.

(Theorem 7.3) Suppose that the capacity function is bounded. We will prove the theorem under this assumption and then argue the other case.

Let $f$ be the max-flow whose existence is guaranteed by Lemma 7.5. Define

S=S_{f}=\{v:\text{there exists a positive residual $s-v$ path}\}\cup\{s\}.

If $t\notin S$ , then $[S,S^{c}]$ is as $s-t$ cut. Also, if $e\in S\times S^{c}$ , then $c_{f}(e)=0$ as otherwise $e^{+}\in S$ which is a contradiction. As we argued before and by the zero residular property of edges in $S\ timesS^{c}$ , we have that

v(f)=f(S,S^{c})=C(S,S^{c})

and so the theorem is proved as we already have the inequality.

If $t\in S$ , then there is a positive residual path $P$ . If we increase the capacity along the path by $c_{f}(P)$ as in Lemma 7.6 and define a new flow $f^{\prime}$ then $v(f^{\prime})=v(f)+c_{f}(P)$ . This will contradict the maximality of $f$ if we show that it satisfies the capacity constraints. Trivially, the capacity constraint is satisfied for all $e,-e\notin P$ as the $f^{\prime}(e)=f(e)$ for all $e,-e\notin P$ . If $-e\in P$ , then $f^{\prime}(e)\leq f(e)\leq c(e)$ . If $e\in P$ , then $f^{\prime}(e)=f(e)+c_{f}(p)\leq f(e)+c_{f}(e)=c(e)$ and so the capacity constraint is satisfied everywhere and the proof is complete.

Now let us assume that the capacity function is unbounded. But since the min-cut is finite, choose a cut $[A,A^{c}]$ such that $c(A,A^{c})<\infty$ . Define $c^{\prime}$ such that $c^{\prime}(e)=c(e)\mathbf{1}[c(e)<\infty]+c(A,A^{c})\mathbf{1}[c(e)=\infty]$ . Observe that the min-cut under $c^{\prime}$ is same as that in $c$ . Further, if a flow is feasible w.r.t $c^{\prime}$ then it is feasible w.r.t. $c$ as well. Since $c^{\prime}$ is a bounded capacity function, we have a max-flow $f$ such that $v(f)=$ min-cut under $c^{\prime}$ . But then, it also holds that $v(f)=$ min-cut under $c$ and $f$ is feasible under $c$ as well. ∎

Exercise(A) 7.8.

The last part of the proof shows that Lemma 7.5 holds under the assumption of finite min-cut alone i.e., the assumption of bounded capacity can be relaxed considerably. Give a direct proof of this without using Max-flow Min-cut theorem.

Theorem 7.9.

Assume that the min-cut is finite. F-F Algorithm terminates if the capacities are integral and also gives that if capacities are integral, there is an integral maximal flow.

Proof.

If capacities are integral, the min-cut is integral and so is the max-flow. At evey step the F-F algorithm increases the flow strength by at least one as the residual capacity along any augmenting path is a positive integer . Since the max-flow is finite, in finitely many steps the algorithm outputs the max flow.

The algorithm starts with $f\equiv 0$ and at every step, the flow on any edge is increased/decreased by the residual capcity if the edge is in a $f$ -augmenting path. Since the residual capacity is integral, the flow is always integral and so is the max-flow. ∎

Example 7.10.

The F-F algorithm need not terminate when capacities are non-integral and here is an example. See https://en.wikipedia.org/wiki/Ford_Fulkerson_algorithm#Non-terminating_example

The definition of a flow can be extended to multiple sources and targets. Let $S\subset V,T\subset V$ be the sources and sinks respectively. The definition of flow can be modified by requiring the Kirchoff’s node law to hold for all $x\notin S\cup T$ and positive output at $S$ i.e., $\sum_{s\in S}(d^{*}f)(s)\geq 0$ . An $S-T$ cut is $A\subset V$ such that $S\subset A,T\subset A^{c}$ . We again have a max-flow min-cut theorem as follows.

Theorem 7.11 (Max-flow min-cut theorem for multiple sources and sinks.).

\max\{v(f):f\,\,\mbox{is a feasible $S-T$-flow}\}=\inf_{A\subset V:S\subset A,% T\subset A^{c}}C(A,A^{c}).

Proof.

Let us again assume that the min-cut is finite i.e., there is no infinite capacity $S-T$ path. The trivial inequality follows as in the original theorem and also the fact that the supremum is maximum. To argue the equality, instead of repeating the proof, we shall use a reduction. Define $G^{\prime}$ as follows : $V^{\prime}=V\cup\{a,b\},E^{\prime}=E\cup(a\times S)\cup(T\times b)$ . Set the capacity of the new edges to be infinite. Note that any $S-T$ cut in $G$ is a $a-b$ cut in $G^{\prime}$ . Further, any $a-b$ cut involving edges in $E^{\prime}\setminus E$ has infinite capacity. Hence the min $a-b$ cut in $G^{\prime}$ and $G$ are equal.

If $f^{\prime}$ is a $a-b$ flow in $G^{\prime}$ , let $f$ be the restriction of $f^{\prime}$ to $G$ . Clearly $f$ is skew-symmetric and satisfies Kirchoff’s node law. We verify the last condition as follows : By Kirchoff’s node law in $G^{\prime}$ , we have that

0=\sum_{s\in S}(d^{*}f^{\prime})(s)=\sum_{e:e^{-}\in S,e^{+}\in V}f(e)+\sum_{e% :e^{-}\in S,e^{+}=a}f(e)=\sum_{s\in S}(d^{*}f)(s)-(d^{*}f^{\prime})(a).

Thus, $v(f)=\sum_{s\in S}(d^{*}f)(s)=(d^{*}f^{\prime})(a)=v(f^{\prime})\geq 0$ and so the max-flow in $G^{\prime}$ is equal to the max-flow in $G$ . Hence the theorem follows from the single-source single-sink max-flow min-cut theorem. ∎

A more general version of max-flow min-cut theorem is as follows : Let $G=(V,E)$ be a directed graph i.e., $e=(x,y)\in E$ does not imply that $-e=(y,x)\in E$ . Let $s,t\in V$ and $c:E\to[0,\infty]$ be a capacity constraint function. Here even if $e,-e\in E$ , $c(e)\neq c(-e)$ . Then $f:E\to[0,\infty)$ is a $s-t$ flow if

1.

$\sum_{e:e^{-}=x}f(e)=\sum_{e:e^{+}=x}f(e)$ for all $x\neq s,t.$ (conservation of flow / Kirchoff’s node law).
2.

$|f|:=\sum_{e:e^{-}=s}f(e)-\sum_{e:e^{+}=s}f(e)\geq 0$ . (flow strength is non-negative.)

As before, we say that $f$ is a feasible flow (i.e., satisfies capacity constraint $c$ ) if for all $e\in E$ , $f(e)\leq c(e)$ . As before, a subset $S\subset V$ is a directed $s-t$ cut if $s\in S,t\notin S$ . Further capcity of a cut is defined as $c(S):=\sum_{e\in E\cap(S\times S^{c})}c(e).$

Figure 7.1: The arrows are labelled with a/b where a is the flow passing and b is its capacity. The dotted line shows a min cut. This shows the equality of max flow and min cut in a directed graph

Exercise(A) 7.12.

(Max-flow min-cut theorem for directed graphs.) Under the notation as above, we have that

\sup\{|f|:\mbox{f is a $s-t$ flow satisfying capacity constraint $c$ }\}=\min% \{C(S):\mbox{$S\subset E$ is an $s-t$ cut}\}.

Proof Sketch : The case of infinite min-cut and infinite capacities can be handled as in the undirected version. So let us assume that capacity is bounded i.e., $c:E\to[0,\infty)$ .

An $f$ -augmenting $x-y$ path is a path $P:x=x_{0},\ldots,x_{k}=y$ such that for each $1\leq i\leq k$ either (i) $c(x_{i-1},x_{i})-f(x_{i-1},x_{i})>0$ or (ii) $f(x_{i},x_{i-1})>0$ . In simple words, either the ‘forward’ edges are not of full capacity or the ‘backward’ edges have positive flow. Define $c_{f}(x_{i-1},x_{i})=c(x_{i-1},x_{i})-f(x_{i-1},x_{i})$ in Case (i) and $c_{f}(x_{i-1},x_{i})=f(x_{i},x_{i-1})$ in Case (ii). If both cases hold, pick one arbitarily as $c_{f}(x_{i-1},x_{i})$ . As before set $c_{f}(P)=\min c_{f}(x_{i-1},x_{i})$ . Show that the flow can be increased by adding $c_{f}(P)$ to the ‘forward’ edges and subtracting $c_{f}(P)$ from the ‘backward’ edges. Now use the proof idea of Theorem 7.3 to complete the proof.

A general version of max-flow min-cut theorem is stated in the exercises.

Exercise(A) 7.13.

Use max-flow min-cut theorem for directed graphs to show the undirected version.

Exercise(A) 7.14.

What is the equivalent of Ford-Fulkerson algorithm for flows on directed graphs.

Exercise(A) 7.15.

Does the F-F algorithm terminate is the capacities are rational ?