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) + Mdelta

• 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