Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Karger’s Algorithm
3.
Algorithm
4.
Example
5.
Implementation
5.1.
Output
6.
Complexity Analysis
6.1.
Time Complexity
6.2.
Space Complexity
7.
Applications
8.
Frequently Asked Questions
8.1.
What is a cut in graph theory?
8.2.
What is the minimum cut?
8.3.
What are disjoint sets?
8.4.
Why does the Karger algorithm give the wrong output?
8.5.
What does edge contraction mean?
9.
Conclusion
Last Updated: Mar 27, 2024
Hard

Implementations and Applications of Karger’s Algorithm for Minimum Cut

Author Ayushi Goyal
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

A cut is the partition of vertices into two or more disjoint subsets.

Minimum cut refers to removing the minimum number of edges from a graph to divide it into two disjoint sets. 

Introduction

This article will discuss the Implementations and Applications of Karger’s algorithm for Minimum Cut. 

Karger’s Algorithm

Karger's algorithm is an algorithm that uses random numbers to compute a minimum cut of a graph G having V and E number of vertices and edges.  

karger algorithm

The main idea is to use the concept of edge contraction, where edge contraction means merging two vertices into one node termed a supernode. All the edges connecting either to ‘u’ or ‘v’ (any two random vertices) are now attached to that supernode as follows-  

example

In Karger’s algorithm, a randomly chosen edge is contracted according to the resulting supernode. This process continues until you have only two supernodes left in the graph. Those two supernodes represent the minimum cut in graph G. 

Before getting into the Implementations and Applications of Karger’s algorithm for Minimum Cut, let’s first understand its algorithm. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm

  • Make a copy of graph G, termed a contracted graph.
  • While contracted graph contains more than two vertices, i.e., while(v > 2)
    • Select any random edge from ‘u’ to ‘v’ of this contracted graph.
    • Merge the vertices ‘u’ and ‘v’ into a supernode and compress the edge. 
    • Remove loops (if formed).
  • After the end of the while loop, only two vertices are left, and the edges connecting those two vertices represent the minimum cut of the graph.

Example

Take an undirected graph having six vertices and nine edges. 

graph representation

Step 1: Combine vertex 2 and 3 by compressing edge C. Then adjust other edges accordingly. 

 step 1 combination

Step 2: Combine vertex 1 and 4 by compressing edge H. Then adjust other edges accordingly. 

step 2 combination

Step 3: Combine vertex 2,3 and 5 by compressing edges G and E. Then adjust other edges accordingly.

step 3 combination

Step 4: Now combine vertices 1,4 and 2,3,5 to make one supernode of all {1,2,3,4,5} you can remove the edge A and F to make the graph disconnected to divide into two components. 

minimum cut

Step 5: Two components of the graph will be separated as follows:  

final representation

Below, the program shows the implementation part of implementations and applications of Karger’s algorithm for minimum cut.

Implementation

#include<bits/stdc++.h>
using namespace std;

// Creating edge class
class Edge{
public:
    // Declaring endpoints u and v
    int u;
    int v;    

    //Constructor
    Edge(){};

    // Creating constructor for giving values
    Edge(int U,int V)
    {
        u=U;
        v=V;
    }
};

// Creating class for the minimum cut
class MinCut{
public:
    int V, E;
    int *parent;
    int *r;
    
    // Constructor for giving value
    MinCut(int v, int e){
        V=v;
        E=e;
        parent=new int[V];
        r=new int[V];

        // Initializing parent and rank (r)
        for(int i=0;i<V;i++)
        {
            parent[i]=i;
            r[i]=0;
        }
    }

    // Function to find minimum using karger algorithm. 
    int minCutKarger(Edge edges[]){
        int vertices=V;
        
        // Run loop till vertices is greater than 2. 
        while(vertices>2)
        {
            // Generating a random integer 
            int rd = rand()%E;

            // Finding leader element of edges[rd].u belongs.
            int set1=find(edges[rd].u);

            // Finding leader element of edges[rd].v belongs.
            int set2=find(edges[rd].v);
            
            // Print the edge if they belong to a different set.
            if(set1 != set2)
            {
                cout<<"\nVertices to be combined - "<<edges[rd].u<<" and "<<edges[rd].v;

                // Making supernode of vertices u and v
                Supernode(edges[rd].u,edges[rd].v);

                // Decrement vertex value.
                vertices--;
            }
        }        

        cout<<"\n\nEdges removed - "<<endl;
        // Initializing answer (minCut) to 0.
        int ans=0;
        
        for(int i=0;i<E;i++)
        {
            // Finding leader element of edges[rd].u belongs.
            int set1=find(edges[i].u);

            // Finding leader element of edges[rd].v belongs.
            int set2 =find(edges[i].v);
      
            // If they belong to a different set, then print edges.
            if(set1!=set2)
            {
                cout<<edges[i].u<<" <----> "<<edges[i].v<<endl;
                
                // Increment ans variable. 
                ans++;
            }
        }
        return ans;
    }
    
    // Function to fint the node
    int find(int node){
        // Compare the parent node and the root node.
        if(node==parent[node]) return node;
       
        // Else, compress the edges.
        return parent[node] = find(parent[node]);
    }

    // Function to make supernode
    void Supernode(int u , int v){
        u = find(u);
        v = find(v);

        // Compare u and v. They belong to the same tree if they are equal.
        if(u!=v)
        {
            // Finding trees with smaller depths.
            if(r[u]<r[v])
            {
                int temp=u;
                u=v;
                v=temp;
            }
            // Attaching the lower rank tree to the higher one. 
            parent[v]=u;
       
            // If now ranks are equal, increasing the rank of u. 
            if(r[u]==r[v])
                r[u]++;
        }
    }
};

int main(){
    int V=5,E=8;

    // Create an Object of class MinCut. 
    MinCut obj(V,E);

    // Creating an array of edges.
    Edge *edge=new Edge[E];
   
    // Creating graph 
    edge[0]=Edge(0,4);
    edge[1]=Edge(0,5);
    edge[2]=Edge(0,1);
    edge[3]=Edge(5,3);
    edge[4]=Edge(1,2);
    edge[5]=Edge(1,3);
    edge[6]=Edge(3,2);
    edge[7]=Edge(2,4);

    // Finding the size of the minimum cut. 
    int count = obj.minCutKarger(edge);
    cout<<"\nNo of edges removed = "<<count;
    return 0;
}


Representation of graph taken in implementation

graph representation

Output

output

Let’s now discuss the complexities of the implementations and applications of Karger’s algorithm for minimum cut.

Complexity Analysis

Time Complexity

The time complexity of Karger’s algorithm is O( E * α(V) ) where (α = alpha) for a graph G having V vertices and E edges because, in every iteration, you are contracting the edges by creating supernodes in the contracted graph.

And in terms of the number of vertices, the time complexity is O(V^2). 

time complexity

Explanation:

As for  V<10^600, O(α(V)) is approximately equal to O(1). So, O(E∗α(V)) = O(E * 1), and the maximum number of edges in a graph is the order of V^2; therefore, O(E) = O(V^2).

Space Complexity

O(V), where V is the size of the array.

Explanation: Storing all the array elements consumes O(V) space.

We have already discussed the implementation part, now discuss the application part of “Implementations and Applications of Karger’s algorithm for Minimum Cut”. 

Applications

  • It can be used to study network reliability, i.e., the smallest number of links that can cause the failure of the entire network. 
  • It is used in recommendation systems. 
  • Split large graphs into smaller ones to ease the computation. 
  • It is used to segment an image, i.e., separating the foreground and background of an image.
  • It is used for detecting weak ties in a graph.
  • In wartime, it is used to know the minimum number of roads needed to be destroyed to block connectivity. 

Frequently Asked Questions

What is a cut in graph theory?

A cut refers to the partition of vertices of a graph into two or more disjoint subsets.

What is the minimum cut?

Minimum cut is defined as the minimum number of edges, when removed from a graph, divide the graph into two disjoint sets.

What are disjoint sets?

Two sets are called disjoint sets if the intersection of two sets is NULL. A Disjoint-Set data structure that keeps records of a set of elements partitioned into several non-overlapping (Disjoint) subsets.

Why does the Karger algorithm give the wrong output?

The Karger algorithm is a “Monte Carlo” algorithm based on random outcomes. So it can also give wrong answers. 

What does edge contraction mean?

Edge contraction means merging two nodes (say u and v) of the graph G into one node, also termed a supernode. 

Conclusion

The above blog covers the implementations and applications of Karger’s algorithm for minimum cut. We discussed what Karger’s algorithm is and what is the time and space complexity of the algorithm. 

After reading this article on the implementations and applications of Karger’s algorithm for minimum cut, you might want to read other related articles. So below are the links for the same:

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations. Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy Coding!

Previous article
Weakly Connected Components in a Directed Graph
Next article
Karp’s Minimum Mean (or Average) Weight Cycle Algorithm
Live masterclass