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 f_in(v)) equals total +ve flow going out of v (or f_out(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, c_f(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 G_f, 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.

 

f_p(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)+f_p(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,
• • G_f has no augmenting path
  • • Proof:
    • • |f’| = |f| + |f_p| 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 G_f , 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 G_f

• Let P be any (not necessarily simple, simple makes it the generic flow algorithm) s-t path in G_f
• f’= augment(f, P)
• Update f to be f’
• Update the residual graph G_f to be G_f^’

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(m²n).

Proof that running time is O(m²n):

• 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 L_i to L_i+1 was removed, L_i+1 to L_i 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(m²n).

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(n²m).

Advertisements