Karger's Algorithm for Minimum Cut

Learn via video course
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
Start Learning
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
Start Learning
Topics Covered


In graph theory, a cut is a set of edges removal of which divides a connected graph into two non-overlapping (disjoint) subsets. The minimum cut (or min-cut) is defined as the minimum number of edges, when removed from a graph, divide the graph into two disjoint sets.

A randomized contraction algorithm i.e.i.e. Karger's Algorithm is used to find the minimum cut of a graph in data structure.


Karger's Algorithm is a randomized algorithm whose runtime is deterministic; that is, on every run, the time to execute will be bounded by a fixed time function in the size of the input but the algorithm may return a wrong answer with a small probability.

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 GG has 55 vertices and 66 edges - minimum cut example one

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

minimum cut example two

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 GG can be defined as cut with minimum size i.e.i.e. there is no other possible cut in the graph GG 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, ABA\leftrightarrow B and DCD\leftrightarrow C.

minimum cut example three

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)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 uu and vv) of the graph GG into one node which is also termed as a supernode. All the edges connecting either to uu or vv are now attached to the merged node (supernode) which may result in a multigraph as shown in the image given below -

karger's algorithm to find min cut

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 GG.

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.


  • Make a copy of graph GG which will be termed as CGCG (contracted graph).
  • While CGCG contains more than two vertices
    • Select any random edge uvu\leftrightarrow v from the contracted graph.
    • Contract the edge and merge the vertices uu and vv 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.


Let GG be the given undirected graph with 55 vertices and 77 edges for which we are interested to calculate minimum cut - kargers algorithm to find min cut example one

  • Step 1 -

    We choose edge aa to contract, nodes 11 and 44 will be merged into one supernode and all edges connecting them will be adjusted accordingly.

    Then the contracted graph will look like : kargers algorithm to find min cut step one

  • Step 2-

    This time we select the edge cc for contracting, so nodes 22 and 33 will be merged and after merging endpoints of the edge cc, the contracted graph (CG)(CG) will look like kargers algorithm to find min cut step two

  • Step 3 -

    Now in our contracted graph, we choose edge ee for contracting hence supernodes {1,4}\{1,4\} and {2,3}\{2,3\} will get merged, and edges ff and gg will get attached to resultant supernode {1,4,2,3}\{1, 4, 2, 3\}. kargers algorithm to find min cut step three

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

    resultant contracted graph


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)find(node) operation and contracting an edge uvu\leftrightarrow v using union(u,v)union(u, v) operation.

In the underlying pseudocode edgesedges denotes the list of all the edges of graph G,G, VV and EE represents number of vertices and edges present in it respectively.


Before seeing the code of Karger's algorithm let's see the blueprint of the code i.e.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 GG, where edge[i]edge[i] is pair of vertices {u,v}.\{u,v\}.

Expected Output -

Size of minimum cut of the graph.

Data Members -

  • VV - Represents the number of vertices in the graph.
  • EE - Represents the number of edges in the graph.
  • parentparent - A integer type array, (Please refer implementation of DSU for detailed explanation)
  • rankrank - 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 GG 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 uu and vv 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 GG with VV vertices and EE edges when it is implemented by using the most optimized DSU approach is O(Eα(V))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<10600,V<10^{600}, O(α(V))O(1)O(\alpha(V))\simeq O(1). So we can write O(Eα(V))O(E*\alpha(V)) == O(E)O(E) and since maximum number of edges in a graph is order of V2V^2 therefore in terms of VV time complexity can be rewritten as O(V2)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/n21/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 VV hence the space complexity is O(V)O(V).

Applications of the Minimum Cut

  • It can be used to get an idea about the reliability of a network i.e.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.i.e. separating foreground and background of an image.


  • The minimum number of edges needed to be removed to disconnect a connected, unweighted, undirected graph into two components denotes the size of the minimum cut of the graph.
  • Karger's algorithm is a randomized algorithm that takes O(V2)O(V^2) time to find the minimum cut of a graph with a certain probability.
  • Minimum cut finds its application in various domains such as network optmizations, image segmenation etc.