# Monday, October 7, 2012 Max flow-Min Cut & Bipartite Matching

### 1Max-Flow Min-Cut Theorem¶

• Definition of a Cut: a partition of the vertices of a graph into two disjoint subsets. (Wikipedia)
• Capacity/Size of a cut is Sum of capacity of edges in the cut-set (edges whose endpoints are in different set)
• Minimum cut is thus the set of edges that sum up to the smallest capacity.
• Claim: Suppose f* is the output of Ford-Fulkerson Max-Flow Algorithm
• There exists a Cut (A , B ) = V(f*).
• Proof: Let A* be the set of all vertices that can be reached from s (source) in the residual graph.

• Consider that edges from s to t in a residual graph represent left-over capacity at that edges. Edges from t to s in residual graph may represent flow from s to t.
• Graph Gf* :
")
• Since the algorithm terminated, we know t cannot be in A* . Otherwise, there will be a path from s to t to augment, thus continue the algorithm.
• Note: No edge should be going from A to B in Gf*.
• For every edge e from A to B , we have f(e)=Ce: otherwise, an edge would exist connecting endpoints in Gf *. i.e: path from A to B must be use in its full capacity, or there will be left over to produce reverse in residual graph.
• For every edge e from B to A, we have f(e)=0 : otherwise, an edge would exist connecting endpoints in Gf *. i.e: edge from B to A become residual edge from A to B if flow > 0, thus must have zero flow.

V(f*) = Sum of flow of edges from A* to B* - Sum of flow of edges from B* to A*
= Sum of capacity of edges from A* to B* - 0
= Cap. ( A*, B*)

V(f*) <= max flow <= min cut <= Cap(A*, B*)
and  V(f*) = Cap(A*, B*)
then V(f*) = max flow = min cut = Cap(A*, B*)

• Random Question: Is it true that every max flow assigns integer values to all edges?

• No, by counter example:

#### 1.1Choosing a good path to augment?¶

• want the largest augment path to be picked ==> slow, poly time
• instead, start with a large value delta, and keep augmenting path with bottleneck >= delta until no such a path remain. Then set delta = delta/2 and continue.
##### 1.1.1Scaling Max-Flow Algorithm¶
    initially, f(e)=0 for all e in E,
set _delta_ = smallest power of 2 >= max capacity of any edge

while _delta_ >= 1:
while exists s-t path "p" in Gf(delta):
augment p.
update Gf(delta).
end while
_delta_= _delta_/2
end while

let Gf(**delta**) be the subgraph of Gf with only edges with residual capacity >= _delta_

• Proof of Correctness : when algorithm terminates, there won't be any s-t path in Gf.(same as Ford-Fulkerson)
• Runtime:

Let C = Max (e in E) Ce. initial _delta_ <= 2C
The outer while loop iterations = log(initial _delta_) <= O(log C)
The runtime of inner loop is bit tough (case dependent)

• Claim: let f be a flow at the end of the delta phase (i.e no s-t path left in Gf(delta) )
• exits a Cut(A,B) in G such that Cap(A,B) <= V(f) + M * delta where M = # of edges in G
• Proof: Let A be the set of vertices that can be reach from s in Gf(delta)
• Observation:

there is no residual edges from A -> B in Gf(delta).
so for every edge e in G from A->B, Ce-f(e) < delta, Ce -delta < f(e)
i.e cannot be augmented anymore.

V(f) = f out (A) - f in (A)
= Sum of f(e) for e from A->B - Sum of f(e) for e from B->A
> Sum (Ce - delta) for e from A->B - Sum of delta for e from B -> A
|------->at most Mdelta
V(f) > Cap(A,B) - M * delta
=> Cap(A,B) < V(f) + M
delta

• Claim: the number of augmentation on the delta - phase is at most 2M

• Proof: Let f^prev denotes the flow at the end of the previous phase. (2delta phase)

• V(f) <= Cap(A,B) <= V(fprev) + 2M
• Observation: every augmentation in the delta-phase adds at least delta to V(f). so we can do at most 2M augmentation: V(f) - V (f prev) <= 2deltaM.

• total running time is:

O(Log C * M * M ) = O(M^2 log C) ---> Polytime
|--augment |--do augmentation

### 1.2Bipartite Matching Problem¶

• Definition: A matching in a graph G is a set of edges with no intersection.
• A prefect matching is a matching including all vertices.
• The Problem:

• input: bipartite graph G, find a largest possible matching in G.
• convert G to a flow network G', s.t the max-flow in G' corresponds to a max match in G.
• construct G' like this ( G partions to (X,Y)):
• direct every edge in G from X to Y and add capacity of 1
• add a node "s" and direct edges from s to every edge iin X with Cap=1.
• add a node "t" and direct edges from every edges in Y to "t" with Cap=1.
• Prop: Max-Flow of G' = Max Matching in G.

• Claim: Max-Flow in G' >= Max matching in G
• Proof: Let M be a max matching in G,

• assign flow of 1 to every edge in M
• assign flow of 1 to every edge from s to a vertex in M, and from every vertex in "?" involved in M to t.
• all other edges get a flow of zero.
• note that V(f) = M, so max flow >= f = M
• Claim: Max-Flow <= Max Matching.

• Proof: let f be a max flow with integer values.
• the edges that get a flow of 1 from X -> Y will form a matching
• since:
• there can only be 1 such X->Y edge incident to any one vertex in X (or in Y).
• so there is a matching M of size >= max-flow
• Max-Matching >= M >= Max-Flow
• thus: Max-Matching >= Max Flow. Max-Flow >= Max-Matching==> Max Flow = Max Matching

Note incomplete:under development