# Graph Algorithms : Network Flow

Definition of a Flow Network:
A directed graph (V,E) with the following properties:
• Associated with each edge e is a capacity c(e) , c(e)>0.
• There is a single source node s belonging to V
• There is a single sink node t belonging to V
Nodes other than s and t are called internal nodes.
Assumptions:
• All capacities are integers.
• There must be at least one edge leaving source
• There must be at least one edge entering the sink
Defining Flow: Basically carrying traffic or flow. More formally, flow is a function mapping each edge to a value f(e) satisfying the following three constraints:
• {Capacity Constraint} For each edge e,  f(e)<=c(e)
• {Skew Symmetry} For each pair of vertices u,v ,  f(u,v) = -f(v,u)
• {Flow Conservation} For each node v other than s and t,  sum of all flow going out of v must be zero. In other words, total +ve flow coming into v (or fin(v)) equals total +ve flow going out of v (or fout(v)).
Hence f can be both negative or positive, also called the net flow of that edge. The value of network flow is thence summation of flow going out of source.
Note: Generally flow for an edge corresponds to the positive flow.
Defining Flow between sets:
f(X,Y) = sum of f(x,y) , x belongs to X, y belongs to Y.
Some Basic Identities:
• f(X,X) = 0
• f(X,Y) = -f(Y,X)
• f(XUY,Z) =  f(X,Z) + f(Y,Z) if X and Y are disjoint.
• f(s,V) = f(V,t)
Proof:
f(s,V)
= f(V,V) – f(V-s,V)
= f(V,V-s)
= f(V,t) + f(V,V-s-t)
= f(V,t) – f(V-s-t,V)
= f(V,t)

The Maximum-Flow Problem

Natural Goal – Maximizing the flow from source to sink without violating capacity constraints.
Note: Problem for multiple sources and sinks can be reduced making a global source and a global sink and connecting with infinite capacities.

Example: Formulate maximum flow as linear programming problem.

Designing The Algorithm:
• DP won’t work here.
• If start with a greedy approach then we can counter that by compensating some flows and directing it to other edges.
• Hence the concept of augmenting paths

Residual Graph: G’ defined w.r.t. some flow f. • Node set of G’ same as G
• Consists of edges that can admit more net flow.
• For every edge having flow less than capacity (assuming forward to be the direction of the capacity)
• A forward edge with residual capacity
• A backward edge describing the flow for that edge
• Mathematically, cf(u,v)=c(u,v)-f(u,v) {c(u,v) will be zero for the reverse edge in nearly all cases}

Note: If f is a flow in G and  f’ is a flow in Gf, then f+f’ is also a flow in G. Proof is trivial using the definition of flow network.
Augmenting Flow using the residual graph:
For any residual graph G’ , a simple path P with the bottleneck edge b as the minimum cost edge in P is called an augmenting path.

fp(u,v): b if (u,v) belongs to P, -b if (v,u) belongs to P, 0 otherwise.

Augmenting flow is defined as f’(u,v) = f(u,v)+fp(u,v)
Proof of f’ being a flow:

If e is a forward edge on P ->  0 <= f(e) <=  f’(e) = f(e) + b <=  f(e) + (ce – f(e)) = ce;
If e is a backward edge on P -> ce >= f(e) >= f’(e) = f(e) – b >= f(e) – f(e) = 0;
Proof for conservation of each node:
If node not in P, no effect. If node is in P then one outgoing flow increases and one incoming flow decreases by the same amount.
Flows and Cuts:
Notion of Cut:  partition the nodes into two sets S & T, s belongs to S, t belongs to T. Then (S,T) form a cut.
Identity: Flow of a cut ( f(S,T) ) equals f(s,V).
Proof:
• f(S,T)
• = f(S,V-S)
• = f(S,V)
• = f(s,V) + f(V-s,V)
• = f(s,V)
• = |f|
Capacity of the Cut: c(S,T) sum of capacities of all edges from S to T.
Theorem: Max Flow = Min Cut for a flow network.
Proof:
• Any Flow <= Capacity of any Cut
• Trivial
• If f is maximum,
• Gf has no augmenting path
• Proof:
• |f’| = |f| + |fp| hence flow increasing with each augmentation.
• |f| = c(S,T) for some S,T
• Proof:
• Take S as all nodes reachable from s in the Residual Graph.
• As t is not reachable from s, S must not contain t.
• Take T as V-S.
• As there are no outgoing edges from S to T in Gf , f(S,T) must be equal to c(S,T).
Ford-Fulkerson Algorithm for finding Max-Flow:
Max-Flow
Initially f(e)=0 for all e in G
While there is an s-t path in the residual graph Gf
• Let P be any (not necessarily simple, simple makes it the generic flow algorithm) s-t path in Gf
• f’= augment(f, P)
• Update f to be f’
• Update the residual graph Gf to be Gf
Endwhile
Return
Points to remember:
• After every augmentation, the flow values and residual capacities are integers
• While augmenting the flow is taken along the direction of the path.
• The total value of flow increases by the bottleneck edge of s-t path cost as all other points conserved
• At most |F| iterations where |F| is maximum flow.
• Hence running time at most O(m|F|) as BFS in O(m+n) and n<=2*m as all nodes have at least one incident edge.
Edmond-Karp Algorithm for finding Max-Flow:
Same as the Generic flow algorithm, with augmentation done only with shortest BFS paths (edge weights as 1).
Running Time With This Modification: O(m2n).
Proof that running time is O(m2n):
• Let δ(s,v) be the level of v in BFS tree.
• After an augmentation, for each edge:
• Either a backward edge is added (if existing was forward)
• Or a forward edge is added (if existing was backward)
• Which means, in a BFS tree, if Li to Li+1 was removed, Li+1 to Li would be added.
• Hence, δ(s,v) must increase at every iteration.
• If an edge starting at u is chosen as the bottleneck edge, u’s level increases by 2.
• Hence a total of 2m * n/2 edges can be chosen as bottleneck.
• Total no. of iterations <= mn.
• Hence O(m2n).
Final Points:
• The flow returned by Ford-Fulkersen Algorithm is a maximum flow.
• Our time analysis assumes that the capacities are integers.
• Given a flow of maximum value, we can compute s-t cut of minimum capacity in O(m) time.
• In every flow network, the maximum value of  s-t flow is equal to the minimum capacity of s-t cut.
• Dinic’s algorithm computes Max Flow in O(n2m).
Advertisements