CO—Ford and Fulkerson algorithm

The Ford and Fulkerson Algorithm

Definition. augmenting path For a network $(N=(V,E,s,t,b))$ and a flow $f$, an augmenting path is an $s$-$t$ path in the undirected graph from $(V,E)$ and follow properties $1^\circ,2^\circ$.

$1^\circ$ A forward arc $(i,j)$: $f(i,j)<b(i,j)$ $2^\circ$ A backward arc $(i,j)$: $f(i,j)>0$

So by augmenting path we can find a new flow whose value greater than the current flow. So each iteration can increase $\delta$ flow.

$$ \delta=\min_{(i,j)} \begin{cases} b(i,j)-f(i,j) & \text{if }(i,j)\text{ is forward}\\ f(j,i) & \text{if }(i,j)\text{ is backward} \end{cases} $$

To find the augmenting path we define $\text{label}(x)=(L1[x],L2[x])$

$(L1[x])$: the node from which node $x$ has been reached $(L2[x])$: the amount of extra flow that can be brought from $s$ to $x$

For the source $\text{label}(s)=(\phi,+\infty)$ and then other label follow these rules

$1^\circ$ the label is propagated from labeled nodes to adjacent nodes called scanning. Scanning of a node must be carried out completely.

$2^\circ$ the labelling stop as soon as the sink is labelled. o.w. it continues until no node can be scanned.

$3^\circ$ the propagating from $x$ to $y$ follow ① $y$ is adjacent to $x$ ($(x,y)$ is an arc or $(y,x)$ is an arc) ② $y$ is unlabelled

$$ \begin{cases} \text{if }(x,y)\text{ is an arc } \begin{cases} \text{if }f(x,y)<b(x,y):\ L2(y)=\min\{L2(x),b(x,y)-f(x,y)\}\\ \text{if }f(x,y)=b(x,y)\text{ then }y\text{ is not scanned in this step} \end{cases}\\ \text{if }(y,x)\text{ is an arc } \begin{cases} \text{if }f(y,x)>0:\ L1(y)=-x\ \ L2(y)=\min\{L2(x),f(y,x)\}\\ \text{if }f(y,x)=0\text{ then }y\text{ is not scanned in this step} \end{cases} \end{cases} $$

To prevent rescanning of a node set LIST Initialisation $\text{LIST}=\{s\}$

Iteration (until $\text{LIST}=\phi$) $1^\circ$ Select a node $x$ and remove $x$ from the LIST $2^\circ$ Scan $x$ and add all nodes labelled from $x$ to LIST $3^\circ$ If $t$ get labelled, we can reconstruct an augmenting path backwards from $t$ using $L1$ and let $\delta=L2(t)$ then

$$ f\rightarrow f_{\text{new}}= \begin{cases} f(i,j)+\delta & \text{if }(i,j)\text{ forward}\\ f(j,i)-\delta & \text{if }(j,i)\text{ backward} \end{cases} $$

Now, we prove that the Ford and Fulkerson algorithm will stop at the optimal solution and for the rational capacity it will stop in finite step.

Definition. cut $c(W,\overline{W})$ $c(W,\overline{W})=\sum\{b(x,y):x\in W,y\in\overline{W}\},\ (W,\overline{W})\text{ is a partition of }V$ $s\in W,\ t\in\overline{W}$

Lemma. Let $(N=(V,E,s,t,b))$ be a network. For any cut $C(W,\overline{W})$ the flow $V$ $$ V=\sum_{\substack{x\in W,y\in\overline{W}\\(x,y)\in E}} f(x,y)-\sum_{\substack{x\in\overline{W},y\in W\\(x,y)\in E}} f(x,y) $$

proof. The max flow problem follow $$ \sum_{(x,y)\in E} f(x,y)-\sum_{(y,x)\in E} f(y,x)=0 \quad \forall x\in V\setminus\{s,t\} $$ $$ \sum_y f(s,y)=V \quad x=s $$ $$ \sum_y f(y,t)=V \quad x=t $$

$$ \begin{aligned} \sum_{x\in W}\left(\sum_{(x,y)\in E} f(x,y)-\sum_{(y,x)\in E} f(y,x)\right) &=\sum_{x\in W}\sum_{(x,y)\in E} f(x,y)-\sum_{x\in W}\sum_{(y,x)\in E} f(y,x)=V\\ &=\sum_{x\in W}\sum_{\substack{y\in W\\(x,y)\in E}} f(x,y)+\sum_{x\in W}\sum_{\substack{y\in\overline{W}\\(x,y)\in E}} f(x,y) -\sum_{x\in W}\sum_{\substack{y\in W\\(y,x)\in E}} f(y,x)-\sum_{x\in W}\sum_{\substack{y\in\overline{W}\\(y,x)\in E}} f(y,x) \end{aligned} $$

$$ =\sum_{x\in W}\sum_{\substack{y\in W\\(x,y)\in E}} f(x,y)+\sum_{x\in W}\sum_{\substack{y\in\overline{W}\\(x,y)\in E}} f(x,y) -\sum_{y\in W}\sum_{\substack{x\in W\\(x,y)\in E}} f(x,y)-\sum_{x\in W}\sum_{\substack{y\in\overline{W}\\(y,x)\in E}} f(y,x) $$

$$ =\sum_{x\in W}\sum_{\substack{y\in\overline{W}\\(x,y)\in E}} f(x,y)-\sum_{x\in W}\sum_{\substack{y\in\overline{W}\\(y,x)\in E}} f(y,x)=V $$

Theorem. let $(N=(V,E,s,t,b))$ be a network Then (a) the relation $V(f)\leq C(W,\overline{W}) \quad \forall f,\ C(W,\overline{W})$ (b) $\max V(f)=\min C(W,\overline{W})$

proof (a) $$ V=\sum_{x\in W}\sum_{\substack{y\in\overline{W}\\(x,y)\in E}} f(x,y)-\sum_{x\in W}\sum_{\substack{y\in\overline{W}\\(y,x)\in E}} f(y,x) $$ $$ \leq\sum_{x\in W}\sum_{\substack{y\in\overline{W}\\(x,y)\in E}} b(x,y)-0 = C(W,\overline{W}) $$

proof (b) Set the last iteration defined in the last iteration the labelled vertex $W^*,\overline{W}^*=V\setminus W^*$ Since it is the last iteration, so $\text{LIST}=\phi$, which means if $(x,y)$ is an arc: $f(x,y)=b(x,y)$ if $(y,x)$ is an arc: $f(y,x)=0$

$$ \begin{aligned} \text{So }V(f^*)&=\sum_{x\in W^*}\sum_{\substack{y\in\overline{W}^*\\(x,y)\in E}} f(x,y)-\sum_{x\in W^*}\sum_{\substack{y\in\overline{W}^*\\(y,x)\in E}} f(y,x)\\ &=\sum_{x\in W^*}\sum_{\substack{y\in\overline{W}^*\\(x,y)\in E}} b(x,y)-\sum_{x\in W^*}\sum_{\substack{y\in\overline{W}^*\\(y,x)\in E}} 0\\ &=C(W^*,\overline{W}^*) \end{aligned} $$ which means the solution is optimal and the min cut is $C(W^*,\overline{W}^*)$

now, we prove if all capacities in network are rational, the algorithm has finite step. (if capacity is irrational number, the algorithm may not stop )

Theorem2. let $(N=(V,E,s,t,b))$ be a network , $b$ is integer Then the Ford and Fulkerson algorithm will find an integer max-flow and for termination after a finite number of steps if it starts with an integer flow

proof. If the algorithm starts from an integer flow by the definition $\delta\ge1$, so each iteration $V(f')=V(f)+\delta\ge V(f)+1$ and since max-flow problem $\exists$ an optimal solution so at leave $V^*-V^\circ$ step, the algorithm terminate.

Corollary1. Let $(N=(V,E,s,t,b))$ be a network , $b$ is rational $\forall(i,j)\in E$ let $b(i,j)=\frac{p(i,j)}{q(i,j)}\quad p,q$ are integers let $D=\operatorname{lcm}_{(i,j)\in E} q(i,j)\quad D=k_{ij}q(i,j)\quad\forall(i,j)\in E\quad k_{ij}$ is integer

Then the max-flow problem is $$ \begin{aligned} \max V\\ \text{s.t. }&Af+dv=0\\ &f\le b\\ &f\ge0 \end{aligned} $$ equivalent to let $f'=Df\quad V'=DV\quad b'=Db$ $$ \begin{aligned} \max V'\\ \text{s.t. }&Af'+dv'=0\\ &f'\le b'\\ &f'\ge0 \end{aligned} $$ $b(i,j)=\frac{p(i,j)}{q(i,j)}$ so $b'(i,j)=k_{ij}q(i,j)\cdot\frac{p(i,j)}{q(i,j)}=k_{ij}p(i,j)$ is integer So It can be terminate in finite step and the final solution is $f^*=\frac{f'^*}{D}$