Design and Analysis - Karger’s Minimum Cut

Considering the real-world apppcations pke image segmentation where objects that are focused by the camera need to be removed from the image. Here, each pixel is considered as a node and the capacity between these pixels is reduced. The algorithm that is followed is the minimum cut algorithm.

Minimum Cut is the removal of minimum number of edges in a graph (directed or undirected) such that the graph is spanided into multiple separate graphs or disjoint set of vertices.

Let us look at an example for a clearer understanding of disjoint sets achieved

Edges {A, E} and {F, G} are the only ones loosely bonded to be removed easily from the graph. Hence, the minimum cut for the graph would be 2.

The resultant graphs after removing the edges A → E and F → G are {A, B, C, D, G} and {E, F}.

Karger’s Minimum Cut algorithm is a randomized algorithm to find the minimum cut of a graph. It uses the monte carlo approach so it is expected to run within a time constraint and have a minimal error in achieving output. However, if the algorithm is executed multiple times the probabipty of the error is reduced. The graph used in karger’s minimum cut algorithm is undirected graph with no weights.

Karger’s Minimum Cut Algorithm

The karger’s algorithm merges any two nodes in the graph into one node which is known as a supernode. The edge between the two nodes is contracted and the other edges connecting other adjacent vertices can be attached to the supernode.

Algorithm

Step 1 − Choose any random edge [u, v] from the graph G to be contracted.

Step 2 − Merge the vertices to form a supernode and connect the edges of the other adjacent nodes of the vertices to the supernode formed. Remove the self nodes, if any.

Step 3 − Repeat the process until there’s only two nodes left in the contracted graph.

Step 4 − The edges connecting these two nodes are the minimum cut edges.

The algorithm does not always the give the optimal output so the process is repeated multiple times to decrease the probabipty of error.

Pseudocode

Kargers_MinCut(edge, V, E):
   v = V
   while(v > 2):
      i=Random integer in the range [0, E-1]
      s1=find(edge[i].u)
      s2=find(edge[i].v)
      if(s1 != s2):
         v = v-1
         union(u, v)
   mincut=0
   for(i in the range 0 to E-1):
      s1=find(edge[i].u)
      s2=find(edge[i].v)
      if(s1 != s2):
         mincut = mincut + 1
   return mincut

Example

Applying the algorithm on an undirected unweighted graph G {V, E} where V and E are sets of vertices and edges present in the graph, let us find the minimum cut −

Step 1

Choose any edge, say A → B, and contract the edge by merging the two vertices into one supernode. Connect the adjacent vertex edges to the supernode. Remove the self loops, if any.

Step 2

Contract another edge (A, B) → C, so the supernode will become (A, B, C) and the adjacent edges are connected to the newly formed bigger supernode.

Step 3

The node D only has one edge connected to the supernode and one adjacent edge so it will be easier to contract and connect the adjacent edge to the new supernode formed.

Step 4

Among F and E vertices, F is more strongly bonded to the supernode, so the edges connecting F and (A, B, C, D) are contracted.

Step 5

Since there are only two nodes present in the graph, the number of edges are the final minimum cut of the graph. In this case, the minimum cut of given graph is 2.

The minimum cut of the original graph is 2 (E → D and E → F).