Mar 6. Maximum flow and minimum cut II

Let G = (V, E) be a directed graph and each edge (i, j) has a capacity c_{ij} \ge 0. There are two special vertices s, t referred to as the source and the sink respectively. A flow is a vector in \mathbb{R}^E such that 0 \le f_{ij} \le c_{ij} for every edge (i, j). Recall that the value of the flow val(f) = f(s, V) - f(V, s) = f(V, t) - f(t, V).

Recall that the maximum s, t flow is always less than or equal to the capacity of the minimum s,t cut. Let (S, \bar{S}) be a s,t cut in the graph such that s \in S. Then we have:

f(S, V) - f(V, S) = \sum_{i \in S} (f(i,V) - f(V, i)) = f(s, V) - f(V, s) = val(f) = f(S, \bar{S}) + f(S, S) - f(S, S) - f(\bar{S}, S) = f(S, \bar{S}) - f(\bar{S}, S) \le f(S, \bar{S}) \le \sum{i\in S, j \in \bar{S}} c_{ij} = c(S, \bar{S}).

Theorem: For every graph G and capacity c_{ij} \ge 0, the value of the maximum s, t flow is equal to the capacity of the minimum s,t cut.

Proof: We need the following definition.

Augmenting Path: An s to t path P is called an augmenting path if for every forward edge (i, j) \in P we must have f_{ij} < c_{ij} while for every backward edge (i, j) \in P we must have f_{ij}>0. The idea is that we can route more flow from s to t via P by increasing the flow on the forward edges and decreasing the flow on the backward edges. Note that the amount of flow we can send is the minimum of c_{ij} - f_{ij} for every forward edge (i, j) \in P and f_{ij} for every backward edge (i, j) \in P.

Note that if f is a maximum s, t flow then clearly there cannot be any f augmenting paths in G. Let us define the set S = \{ u \mid \exists s, u\text{ augmenting path}\}. Note that for every forward edge (i, j) coming out of S we must have f_{ij} = c_{ij} while for every backward edge (i, j) coming into S we must have f_{ij} = 0. Thus val(f) = \sum_{i \in S, j \in \bar{S}} f_{ij} - \sum_{i \in S, j \in \bar{S}} f_{ji} = \sum_{i \in S, j \in \bar{S}} c_{ij} - 0 = cap(S, \bar{S}).

Residual Graph:  For every edge (i, j) such that the flow f_{ji} = 0 we set the capacity c'_{ij} = c_{ij} - f_{ij} while the capacity of c'_{ji} = f_{ij}. Define the residual graph G' to be the graph on the same set of vertices as G and consisting of edges (i, j) such that c'_{ij} > 0. Note that by definition any s, t augmenting path in G is a directed path in the residual graph G'. Thus finding an augmenting path reduces to finding a directed s, t path in G'.

Choice of augmenting path

  • One could choose the maximum (residual) capacity augmenting path from s, t. The capacity of a path is defined as the minimum of the residual capacity of the edges in the path.
  • Alternatively we could also pick the shortest (number of edges) s, t path in G'.

Claim:  Given a flow f and optimal flow f^* in G then there exists a path in the residual graph of G and f such that its capacity is at least \frac{f^*-f}{m}.

Proof: Observe that in every m step the difference f^* - f becomes at least 1/2 of the initial value. Suppose the original capacities are integral then we can only halve till \log{f^*} \le \log{nC} where C is the largest capacity edge in G. Thus the running time is m\log{nC}. Note that this is polynomial in the size of the input since we need only \log{nC} bits to write down the capacities of all the edges. There is a strongly polynomial algorithm that depends only on m and not on the capacity.

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