Random Contraction Algorithm

1.  Two ingredients of Graph:

    a)  vertices A.K.A. nodes (V)

    b)  edges = pairs of vertices (E)

         can be undirected or directed A.K.A arcs

 

2.  Definition of Cuts of Graphs:

    A cut of Graph ( V, E) is a partition of V into two non-empty sets A and B.

    The crossing edges of a cut (A, B) are those edges with:

    a) one endpoint in each of (A, B)  for undirected graph

    b) tail in A, head in B for directed graph

 

3.  Definition of the Minimum Cut Problem:

    Input : an undirected graph G = (V, E)  , parallel edges (multiple edges for the same node pair are allowed

    Output :  a cut with fewest number of crossing edges.

 

4.  Applications for Min-Cut problem:

    a)  Identify network bottlenecks / weaknesses

    b)  Community detection in social networks

    c)  Image segmentation

 

5.  Let n = # of vertices and m = # of edges.

    In most applications, m is Ω(n) and O(n^2).

    -- in a "Sparse Graph", m is O(n) or close to it.

    -- in a "Dense Graph", m is Θ(n^2) or close to it.

 

6.  The Ajacency Matrix :

    Represent G by a nXn 0-1 matrix A, where Aij = 1 <==> G has an i-j edge

    Variants:

     a)  Aij = # of i-j edges (if parallel edges allowed)

     b)  Aij = weight of i-j edge ( if any)

     c)  Aij = +1, if i --> j ; -1 if j --> i ;

    Takes Θ(n^2) spaces.   

 

7.  The Ajacency Lists:

    a)  array ( or list ) of vertices

    b)  array ( or list ) of edges

    c)  each edge points to its endpoints

    d)  each vertex points to edges incident on it

    Takes Θ(n+m) = Θ (max{n, m}) spaces.

 

8.  Random Contraction Algorithm:

    While there are more than 2 vertices :

    a) pick a remaining edge (u, v) uniformly at random

    b) merge ( or contract ) u and v into a single vertex

    c) remove self-loops

    Return cut represented by final 2 vertices.

 

9.  Fix a graph G = (V, E) with n vertices , m edges.

     Fix a minimum cut (A,B), ( there can be multiple minum cuts, here we fix the specific one)

     Let k = # of edges crossing (A, B)

     Let F = crossing edges of cut (A, B)

     a)  Suppose an edge of F is contracted at some point => algorithm will not output (A, B)

     b)  Suppose only edges inside A or inside B get contracted => algorithm will output (A, B)

     So, P[ output is (A, B) ] = P[ never contracts an edge of F]

     Let Si = event that an edge of F contracted in iteration i.

     Goal : compute P[ !S1 and !S2 and ...and !Sn-2]

     degree ( # of incident edges ) of each vertex is at least k. (otherwise # of crosing edges of min-cut <k)

      Sum {degree(v) } = 2m >= kn , m >= kn/2

      So for the first iteration, P[S1] = k/m <= 2/n. P[!S1] >= 1-2/n

      P[!S1 and !S2] = P[!S1] P[!S2 | !S1] >= (1-2/n) ( 1- k/ # of remaining edges)

      In the second iterfation, still degree(v) >= k , so Sum{degree(v)} = 2 * # remaining edges >= 2 (n-1)

      So P[!S1 and !S2] >= (1-2/n) * (1- 2/(n-1) );

   So P[ never contracts an edge of F]>= ( 1- 2/n ) * ( 1- 2/(n-1) ) * ... * ( 1- 2/(n-(n-3) ) ) (total n-2 iteration)

                                                             = (n-2)/n * (n-3)/(n-1) * (n-4) /(n-2) * ... *   2/4 * 1/3

                                                             = 2/(n * (n-1) ) >= 2/n^2

 

10.  Run the random contraction algorithm a large number N times. Let Ti = event that the Min-Cut (A, B) is found on the ith try. By definition different Ti are independent.

      So P[ all N trials failed] = P [ !T1 and !T2 and ... !TN] = P[!T1] * P[!T2] * ... * P[!TN] <= (1-1/n^2)^N

      Since, for any real number x, 1+x <= e^x

       let N= n^2 , P[ all N trails failed] <= e^(-N* 1/n^2) = 1/e

       let N = n^2* lnn , P[ all N trails failed] <= 1/n

      Each contraction algorithm takes O(m) (need to check each edges) and at most n^2 or n^2 * lnn times.

 

11.  A tree with n vertices has n-1 min cuts.

 

12.  What's the largest number of min cuts that a graph with n vertices can have?

       Lower bound : n verices that forms a cycle. Each pair of the n edges defines a distinct min cut ( with two crossing edges) . so it has n * (n-1) / 2 min cuts.

       Upper bound :  Let (A1, B1) , (A2, B2), ... (At, Bt) be the min cuts of a Graph with n vertices. By random contraction algorithm, we know that P[ output = (Ai, Bi) ] >= 2/(n (n-1) ).

       So Sum(i = 1, 2, ..., t) { P[output = (Ai, Bi)] } >= 2t/( n(n-1) ) <= 1 , so t <= n(n-1) /2