Network Flow
A flow network comprises of :
- A directed graph G(V,E)
- Non-negative capacities on each edge c(u,v)
- A source s
- A sink t
Definition: Flow
Flow is a function f:E\rightarrow \mathbb{R} such that the following properties hold
- Bounded by Capacity: f(u,v) < c(u,v)
- Anti-Symmetry: f(u,v) = -f(v,u)
- Conservation of flow: For any node u that is neither source nor sink, \sum_{v\in V} f(u,v) = 0
- Special vertices s and t such that all flow starts from s and ends at t
Definition: Value of Flow
\text{Value of flow} = |f| = \sum_v f(s,v)
Definition: Residual Capacity
Given the capacity c and flow f, the residual capacity of an edge u \rightarrow v is
\begin{align}
c_f(u,v) = c(u,v) - f(u,v)
\end{align}
Note - Even if there is no directed edge u \rightarrow v in the graph, i.e c(u,v) = 0 it might still have a non-zero residual capacity.
Definition: Residual Graph
For a flow f in a graph G(V,E) the residual graph G_f(V,E_f) is the graph with all edges with positive residual capacity, i.e
E_f = \{(u,v)\in \left(V \times V\right)| c_f(u,v)>0\}
Note - Because of the note above |E_f|<2|E| because each edge in G can induce at most 2 edges in G_f.
Lemma:
The flow generated by adding the flows in the graphs G(V,E) and G_f(V,E_f) is also a valid flow in G with a higher flow value
|f+h| = |f| + |h|
The flow generated by adding the flows in the graphs G(V,E) and G_f(V,E_f) is also a valid flow in G with a higher flow value
|f+h| = |f| + |h|
Note - (f+h)(u,v) is defined as f(u,v) + h(u,v).
Definition: Augmenting Path
For graph G and a flow f, any directed path, \pi from s to t in G_f is called an augmenting path. The maximum flow that can be pushed through \pi is denoted by c_f(\pi) where
c_f(\pi) = \max_{(u\rightarrow v)\in \pi} c_f(u,v)
Note - c_f(\pi) is always positive by definition of Residual Graph.
Lemma: Improving the flow in f using an Augmenting Path
Let f be a flow in G and f_{\pi} be a flow on an augmenting path, \pi, in G_f. The f+f_{\pi} is a better flow in G since |f+f_{\pi}| = |f| + |f_{\pi}| > |f|.
Problem: Max FlowDefinition: Augmenting Path
For graph G and a flow f, any directed path, \pi from s to t in G_f is called an augmenting path. The maximum flow that can be pushed through \pi is denoted by c_f(\pi) where
c_f(\pi) = \max_{(u\rightarrow v)\in \pi} c_f(u,v)
Note - c_f(\pi) is always positive by definition of Residual Graph.
Lemma: Improving the flow in f using an Augmenting Path
Let f be a flow in G and f_{\pi} be a flow on an augmenting path, \pi, in G_f. The f+f_{\pi} is a better flow in G since |f+f_{\pi}| = |f| + |f_{\pi}| > |f|.
Given a network flow, find the maximum flow, i.e, maximum possible value of |f|.
Algorithm: Ford Fulkerson Method
1. Initialize f(u,v) = 0 \; \forall \; (u,v) \in E
2. Compute residual graph G_f
3. Find an augmenting path, \pi, in G_f
4. Update flow in G by f \leftarrow f + f_{\pi}
5. Repeat 2-5 until there are no augmenting paths left in G_f
Definition: Directed Cut
A directed cut (S,T) in a flow network is a partitioning of V into disjoint sets S and T = V\setminus S such that s\in S and t\in T. Standard terminology -
- Net flow of f across a cut (S,T), is f(S,T) = \sum_{u\in S, v\in T}f(u,v)
- Capacity of cut (S,T) is c(S,T) = \sum_{u\in S, v\in T}c(u,v)
- Minimum cut is the cut with the minimum capacity (*\ important \*)
Lemma: Value of flow in network is the flow across any cut
f(S,T) = |f| \; \forall \; \text{cuts} \; (S,T)
(*\Proof is a one liner but worth looking at\*)
Lemma: Flow is bounded above by capacity of any cut (S,T) in G
|f| \leq c(S,T) \; \forall \; \text{cuts} \; (S,T)
Theorem: Max-flow Min-cut
If f is flow in a flow network G(V,E) with source s and sink t, then the following statements are equivalent
A. f is the Max-flow
B. \nexists augmenting path in G_f
C. \exists \; \text{cut} \; (S,T) \ni |f| = c(S,T) and (S,T) is a Min-cut
Proof:
(A \implies B)
If augmenting path \pi did exist in G_f then we could have further improved the flow in G by the amount |f_{\pi}| = c_f(\pi). Hence a contradiction
(B \implies C)
Define S = \{v | v \in V \; and \; \exists \; \text{a path from s to v in} G_f\}. Let T = V \setminus S. Then,
|f| = f(S,T) = \sum_{x\in S, y\in T}f(x,y) = \sum_{x\in S, y\in T}c(x,y) = c(S,T)
Note - If f(x,y) \neq c(x,y), then c_f(x,y) > 0 \implies (x \rightarrow y) is an edge in G_f. This would further have implied that y \in S which contradicts the construction of S.
Also, (S,T) has to be a Min-cut because if it were not then it would have implied that \exists \; cut (S', T') \ni c(S',T') < c(S,T) = |f|. But we know that |f| \leq c(S,T) \; \forall (S',T'). Hence a contradiction.
(C \implies A)
Since |f| is bounded above by the capacity of any cut and we have |f| = c(S,T) for some cut, implies that |f| is the max-flow.
Hence proved.
Conclusion
By Max-cut Min-Flow theorem, it follows that if Ford-Fulkerson terminates then it would be a max-flow. But does Ford-Fulkerson terminates?
Claim: Ford-Fulkerson terminates for integral edge capacities
- Ford Fulkerson only performs additions, subtractions and min operations.
- So if it finds an augmenting path, \pi, then c_f(\pi) is a positive integer, i.e, c_f(\pi) \geq 1.
- In every iteration we would be improving the flow by at least 1.
- If the value of max-flow is |f^*| then in at most |f^*| steps the algorithm will terminal
- In every iteration calculating the augmenting path takes O(|E|) time (BFS or DFS).
- Hence, the algorithm run in O(|f^*| |E|)
Integrality Theorem
If all capacities are integral, then the flow |f| generated by Ford-Fulkerson is integral since max-flow equals min-cut which is integral. Also the flow f(u,v) on every edge is integral.
Algorithm: Edmonds - Karp
It is an efficient implementation of Ford-Fulkerson using BFS to find the shortest augmenting path in each iteration. It is meant to deal with the situation where |f^*| is very large.
Definition:
For a flow f, \delta_f(v) is the length of the shortest path from s to v given that each path is of unit length.
Lemma: \delta_f(v) increases monotonically with every flow augmentation
Lemma: Bound on the number of disappearances of an edge in residual graph
The number of times an edge can disappear (and reappear) in the residual graph is at most |V|/2.
Proof:
- Let f be the flow in the iteration when edge (u\rightarrow v) disappears from G_f
- (u\rightarrow v) must have been in the augmenting path \pi_f
- \delta_f(v) = \delta_f(u) + 1
- Let g be the flow in the iteration when edge (u\rightarrow v) reappears in in G_g
- (v\rightarrow u) must have been in the augmenting path \pi_g
- \delta_g(u) = \delta_g(v) + 1
- By monotonicity of \delta, \delta_g(u) \geq \delta_f(u) + 2
- But \delta_g \leq |V|
- This can happen at most |V|/2 times
Hence proved
Time Complexity of Edmonds - Karp
- In every iteration, at least one edge (namely the one which realizes the residual capacity of the augmenting path in the residual graph) will disappear.
- Total number of disappearances is \frac{|V||E|}{2}
- In each iteration finding the shortest path takes O(|E|) time
- Algorithm runs in O(\frac{|V||E|^2}{2}) time
Applications of Max-Flow
- Maximum Bipartite Matching can be solved in O(|V||E|) time
- There is a simple extension for multiple sources and sinks by simply connecting them with a Super source and sink with edges of infinite capacity
No comments:
Post a Comment