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:
maxFlow01
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.

7761D2BF-F984-459F-B9D4-AB5DC0CC1F5D

  • 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:
maxFlow07
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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s