A Flow Network Problem

Last assignment of this term, last question of it and this one goes like this: Show that a maximum flow in a flow-network G = (V,E) can always be found by sequence of at most |E| augmenting paths.

Let me defragment the question and talk about what is what and then give an intuitive solution.

G is a graph represeting a flow-network with V as set of vertices and E that of edges. |E| is the total number of edges in this graph, or flow-network, G. An augmenting path is a simple path in G, that can accomodate more flow without violating the capacity constraints on an edge. The problem is to prove that we can find maximum flow in G, in atmost |E| sequences of such augmenting paths.

The most intuitive solution is reverse Ford-Fulkerson. What does this algorithm do? It starts by making flow on every edge 0, thus making the total flow 0. It then iterates through a path p from s, source to sink, t as long as there is an augmenting path. When there are no more augmenting paths it terminates and gives the maximum flow, |f|. It calculates this by adding the residual capacity of each edge.

So, in order to solve our problem we go reverse by subtracting this capacity, reducing one edge’s flow to 0 each time, untill we get a total flow of 0. This can happen when flow along all the edges in the path is 0, since there are only |E| edges, we get a sequence of atmost |E| augmenting paths. I think there can be a formal proof too.

Ford-Fulkerson(G,s,t)

1. for each edge (u,v) in E(G)
2. do f[u,v] = 0 and f[v,u] = 0
3. while there exists a path p from s to t in the residual network G(f)
do c = min(c(u,v)-f(u,v): (u,v) is in p)
for each edge (u,v) in p
do f[u,v] += c and f[v,u] = – f[u,v]

The Reverse-Ford-Fulkerson will know the maximum flow, say it is |f[0]| and the path associated with this flow, say P[0]. Let P be the set of all the augmenting paths that we had.

and the Reverse-Ford-Fulkerson is

1. Let i = 0 and P = NULL.
2. while |f[0]| > 0
i++
R[i] = min ( f(u,v): (u,v) as an edge in P[i-1] )
|f[i]| = |f[i-1]| – R[i]
P = P U {P[i]}
return P.length

In the above algorithm, the line 5 reduces the flow along every edge in the path P[i-1] by R[i] and also makes the flow in one of the edge in that path as 0. Every such iteration reduces the flow of the network untill it reaches 0 and making the flow along one of the edge 0.( we hence reach the first 2 steps of the Ford-Fulkerson algorithm). Since there are |E| edges, the length of P returned is atmost |E|.