Monday, October 7, 2012 CC-BY-NC
Max flow-Min Cut & Bipartite Matching

Maintainer: admin

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* :
      Cut (A*,B*)")
    • 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:
      no-integer flow

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

  • 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