This blog talks about a polynomial time algorithm to Max flow problem, called ${ \Delta }$-Ford-Fulkerson Algorithm.

Idea

Our plain idea is find an augmenting path with highest bottleneck capacity in each iteration. However, we can do it in a more efficient way. In each iteration, we augment the path which bottleneck is greater than the threshold $\Delta$.

Consider the Ford-Fulkerson Algorithm, it’s a pseudo-polynomial algorithm because $C$ (the maximum capacity) is annoying. We know the input is $\mathcal{O}(m \lg C )$. So, we hope we can change the factor in running time from $C$ to $\lg C$. Hence, we have following algorithm.

${ \Delta }$-Ford-Fulkerson Algorithm

Pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Param-Ford-Fulkerson(G,s,t,C)
	for each e in E
		f(e) = 0 

​	C = max capacity

​	Δ = 2^([lg C]+1) // smallest power of 2 that greater than C

​	G_f = Residual(G,f)

​	while (Δ >= 1)

​		G_f(Δ) :=  subset of the G_f consisting only of edges with edges with residual capacities at least Δ.

​		while (there exists an augmenting path P in G_f(Δ))

​			f = Augment(f,c, P,Δ)

​			update G_f

​		Δ = Δ/2

​	return f

Correctness

Assumption:

1. All capacities are integers and each capacity equals and less than ${ C }$.

2. Every flow value ${ f(e) }$ are integers.

By integrality, when $\Delta = 1$, we know ${G_f^{\Delta} = G_f}$. By the argue for the Ford-Fulkerson correctness, we can get the above algorithm returns a valid and max flow.

Running time

Lemma 1: The number of loops is ${ 1+ \lceil \lg C \rceil }$.

Proof. It’s trivial to get. $\square$

Lemma 2: Let ${ f }$ be the flow at the end of some ${ \Delta }$ phase. Then if ${ f_{max} }$ be the max flow then

Proof. We will show in the end of ${ \Delta }$ phase, denote the current flow is $f$, ${ \exists }$ cut ${ (A,B) }$ s.t. \(Cap(A,B) \leq v(f) + m \Delta\)

Now we construct cut ${ (A,B) }$ as follow:

$A$: Denote $A$ as the set of nodes that are reachable from $s$ in $G_f^\Delta$.

$B$: $V \setminus A$. (By definition, we know $t \notin A$, so $t \in B$. Otherwise, $t$ is reachable from $s$, that means there still have augmenting path in $\Delta$ phase, which contradicts to the assumption that it’s the end of $\Delta$ phase.)

Claim 1: $\forall e \in \delta^-(A)$, we have $f(e) \leq \Delta$.

Suppose there exists an edge $e = (u,v)$, $u \in B, v \in A$ such that $f(e) > \Delta$. That means its reverse edge $e^R$ will exist in $G_f^\Delta$, so $u$ will be reachable from $s$, which contradicts to the construction of $A$.

Claim 2: $\forall e \in \delta^+(A)$, we have $f(e) \geq c(e) - \Delta$.

Suppose there exists an edge $e = (u,v)$, $u \in A, v \in B$ such that $f(e) < c(e) - \Delta$, that is $c(e) - f(e) \geq \Delta$. That means $e$ will exist in $G_f^\Delta$, so $v$ will be reachable from $s$, which contradicts to the construction of $A$.

By above claims, we have

By Max flow-Min Cut theorem, we know $v(f_\max) \leq Cap(A,B) \leq v(f) + m \Delta$. $\square$

Lemma 3: There are at most ${ 2m }$ augmentations in each iteration.

Proof. At the end some $\Delta$ phase, the flow is $f$. Then by Lemma 2, we have \(v(f_{max}) \leq v(f) + m \Delta\)

That means the increase room of current flow have at most $m \Delta$. In next phase $\frac{\Delta}{2}$, we know each augmenting will increase at least $\Delta/2$ (All the edge with capacity at least $\Delta/2$ in $G_f^{\Delta/2}$). Hence, the times of augmenting in each phase is at most $\frac{m\Delta}{\Delta/2} = 2m$. $\square$

Summary:

By lemma 1-3, we know there are $1+ \lceil \lg C \rceil$ loops, and in each loop we have at most $2m$ augmentation, and each augmentation takes at most $\mathcal{O}(m)$. Hence, the total running time is $\mathcal{O}(m^2 \lg C)$.