Karger's Algorithm for Minimum Cut

Introduction to Minimum Cut

Before discussing Minimum cut, let us first understand what does a Cut means in terms of graph data structure?

A cut can be defined as a partition of vertices of a graph into two or more disjoint subsets.

For example:

The given graph $G$ has $5$ vertices and $6$ edges -

One of the possible cuts in this graph is to partition this graph into two disjoint sets $i.e.$ splitting the graph into two disconnected components, one with vertices $A, B, C \space and\space D$ and the other one with a single vertex $E$ by removing three edges $B\leftrightarrow C,$ $B\leftrightarrow E,$ and $C\leftrightarrow E$ as shown below -

Each cut has some size associated with it, that is the sum of the weights of the edges that have been removed. In the case of un-weighted graphs size is nothing but the number of vertices that have been removed.

Now as suggested by the name, A Minimum cut (or simply a min-cut) of a graph $G$ can be defined as cut with minimum size $i.e.$ there is no other possible cut in the graph $G$ with a smaller size.

In simple words, the minimum number of edges required to remove to disconnect the graph into two components is known as the minimum cut of the graph.

The min-cut of the above-shown graph is shown below which can be obtained by removing two edges, $A\leftrightarrow B$ and $D\leftrightarrow C$.

Karger's Algorithm to Find Min Cut

Karger's algorithm is a randomized algorithm (an algorithm which have some degree of randomness associated in its procedure) to compute a minimum cut of a connected, undirected, and unweighted graph $G=(V,E)$. It is a "Monte Carlo" algorithm which means it may also produce a wrong output with a certain (usually low) probability.

The main idea of Karger's algorithm is based on the concept of edge contraction, where edge contraction means merging two nodes (say $u$ and $v$) of the graph $G$ into one node which is also termed as a supernode. All the edges connecting either to $u$ or $v$ are now attached to the merged node (supernode) which may result in a multigraph as shown in the image given below -

In Karger's algorithm, an edge is chosen randomly, and then the chosen edge is contracted which results in a supernode. The process continues until only two supernodes are remaining in the graph. Those two supernodes represent cut in the original graph $G$.

As Karger algorithm being a "Monte Carlo" algorithm can also give wrong answers so by repeating the algorithm many times the minimum cut of the graph can be found with a certainly high probability.

Algorithm

• Make a copy of graph $G$ which will be termed as $CG$ (contracted graph).
• While $CG$ contains more than two vertices
  • Select any random edge $u\leftrightarrow v$ from the contracted graph.
  • Contract the edge and merge the vertices $u$ and $v$ into one.
  • Remove self-loops (if formed).
• After the above step only two vertices will be remaining in the graph and the edges connecting those two vertices represents the minimum cut of the graph.

Now let us understand how this algorithm finds the minimum cut through an example.

Example

Let $G$ be the given undirected graph with $5$ vertices and $7$ edges for which we are interested to calculate minimum cut -

• Step 1 -

  We choose edge $a$ to contract, nodes $1$ and $4$ will be merged into one supernode and all edges connecting them will be adjusted accordingly.

  Then the contracted graph will look like :

• Step 2-

  This time we select the edge $c$ for contracting, so nodes $2$ and $3$ will be merged and after merging endpoints of the edge $c$, the contracted graph $(CG)$ will look like

• Step 3 -

  Now in our contracted graph, we choose edge $e$ for contracting hence supernodes $\{1,4\}$ and $\{2,3\}$ will get merged, and edges $f$ and $g$ will get attached to resultant supernode $\{1, 4, 2, 3\}$.

  Now our resultant contracted graph contains only two vertices so this is the minimum cut. We can remove edges $f$ and $g$ to disconnect the graph into two components which is also verified by removing them in the original graph in the diagram shown below -

  

Pseudocode

In DSU article we have seen how we can keep record of the sets to which a particular element belongs in almost constant time complexity.

We use the same concept here, to keep track of vertices that belongs to a particular supernode using $find(node)$ operation and contracting an edge $u\leftrightarrow v$ using $union(u, v)$ operation.

In the underlying pseudocode $edges$ denotes the list of all the edges of graph $G,$ $V$ and $E$ represents number of vertices and edges present in it respectively.

Code

Before seeing the code of Karger's algorithm let's see the blueprint of the code $i.e.$ how we are implementing it, what are data members and methods we are using, etc.

Input -

A array/list of edges of the graph $G$, where $edge[i]$ is pair of vertices $\{u,v\}.$

Expected Output -

Size of minimum cut of the graph.

Data Members -

• $V$ - Represents the number of vertices in the graph.
• $E$ - Represents the number of edges in the graph.
• $parent$ - A integer type array, (Please refer implementation of DSU for detailed explanation)
• $rank$ - A integer type array, (Please refer implementation of DSU for detailed explanation)

Methods -

• minCut - It is the main function used to find the minimum cut of the graph by contracting the edges of the graph $G$ till we have been left with only two vertices.

• Find - It is used to check whether two nodes belong to the same supernode or not by checking if the leader of set to which vertices $u$ and $v$ belongs is same or not.

• Union - It is used to merge two nodes into one supernode by using the typical union function as discussed in the DSU article.

C/C++ implementation of Karger's Algorithm

Java implementation of Karger's Algorithm

Output -

Complexity of Karger's Algorithm

The time complexity of Karger's algorithm for a graph $G$ with $V$ vertices and $E$ edges when it is implemented by using the most optimized DSU approach is $O(E*\alpha(V))$ because in every iteration we are contracting the edges in the contracted graph.

Now as we learned in DSU for $V<10^{600},$ $O(\alpha(V))\simeq O(1)$. So we can write $O(E*\alpha(V))$ $=$ $O(E)$ and since maximum number of edges in a graph is order of $V^2$ therefore in terms of $V$ time complexity can be rewritten as $O(V^2)$.

The probability that cut produced by Karger's algorithm is the required min-cut of the graph is greater than or equal to $1/n^2$ which might seem very small. We can improve this probability to an arbitrarily large probability, by repeating the algorithm several times and keeping track of values of size of cut found in each iteration.

To implement DSU we need an array of size $V$ hence the space complexity is $O(V)$.

Applications of the Minimum Cut

• It can be used to get an idea about the reliability of a network $i.e.$ smallest number of links failure of which will lead to failure of the entire network.
• In wartime, to know what is the minimum number of roads needed to be destroyed to block connectivity of an area from other parts of the enemy nation.
• It is used in image segmentation $i.e.$ separating foreground and background of an image.