Check if the Graph can be Divided into Two Cliques

Introduction 🤓

We are playing with the graphs from the middle school. Making flowcharts, connecting two quantities with lines, and measurements, are all a part of our middle school maths syllabus. But ever wonder how you can implement them in the real world!? Well, as a programmer, you need these tools more than anybody else.

This article will discuss how to check if the graph can be divided into two cliques. This problem is popularly known as the two cliques problem. A Clique is a subgraph of the graph. Here all the vertices in the subgraph are completely connected. A graph can only be divided into two cliques if their complement is a Bipartite graph.
 

You should try this problem by yourself before preceding this article. 

Problem Statement 🤔

You are a shinobi of the hidden village of mist. You are assigned a mission to retrieve the scroll of secrets. But the guardian of the scroll is an old turtle. The turtle gave you a problem checking whether you are worthy of the scroll or not. 

The problem is to check if the graph can be divided into two cliques. You are provided with an undirected graph. It will have ‘N’ nodes and ‘M’ edges. Your task is to check whether this graph can be divided into two cliques. If it is possible to divide it into two cliques, you’ll answer him, “Yes, it can be divided”. Otherwise, your answer will be, “No, it can’t”. 

Let’s go through an example to better understand the problem.

Sample Example 🧐

Example 1:

Input:

Output:

Yes, it can be divided into two cliques.

Explanation:

The above graph can be divided into two cliques. {0, 1, 2} and {3, 4, 5}.

Example 2:

Output:

No, it can’t be divided into two cliques.

Explanation: 

The above graph is not isolated enough to break it down into two. Because it is not bipartite. 

Complement Graph Approach 🧑‍💻

Check if the graph can be divided into two cliques for the problem. A complement graph approach is the most suitable approach. Here we find a complement of the given graph and check whether it is bipartite or not. If the complement is a Bipartite graph. Then the graph can be divided into two sets, U and V. 

There should be no edge connecting the same set of vertices. This means in the original graph, these sets U and V are completely connected. Hence original graph could be divided into two Cliques.

Let’s see the algorithm of the given approach.

Algorithm 🧑‍💻✨

1. We will create a function that returns true if the subgraph is reachable from the source. To do so
   1. We will create a queue where we will store vertex numbers.
   2. Then we will enqueue from source vertex for BFS traversal.
   3. Now check for all vertices in the queue
      1. Find all non-colored adjacent vertices in the graph.
      2. Check whether an edge from u to v exists 
      3. And the destination v is coloured or not.
      4. Now assign an alternate colour to the adjacent vertices v of u
          
2. We will create a function which returns true if the graph is bipartite. Else, false. 
   1. We will first create a colour array to store the colours assigned to all vertices.
   2. Now check vertices which are not yet coloured.
       
3. Now we will check whether a function can be divided into two cliques.
   1. Find the complement of the graph.
   2. Here all values are complemented except diagonal ones.
   3. Now return the value true if it is bipartite. Otherwise, return false.

Implementation 🧑‍💻🌝

#include <bits/stdc++.h>
#include <cmath>
#include<algorithm>

using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
const int V = 5;

//--------------------------------Bipartite Utility Function--------------------------------//
bool Bipartitefxn(int G[][V], int src, int coloringarray[])
{
		coloringarray[src] = 1;
		
	// Creating a queue of vertex numbers 
		queue <int> q;
	// and enqueuing source vertex for BFS traversal
		q.push(src);

		while (!q.empty())
		{
			int u = q.front();
			q.pop();

		// Find all non-colored adjacent vertices
				for (int v = 0; v < V; ++v)
				{
					if (G[u][v] && coloringarray[v] == -1)
					{
					// Assigning alternate color
					coloringarray[v] = 1 - coloringarray[u];
					q.push(v);
					}

					else if (G[u][v] && coloringarray[v] == coloringarray[u])
					return false;
				}
		}

	// Now all vertices are colored with alternate color
	return true;
}

// Fuction will check if a Graph is Bipartite or not. Here, G cannot be connected.
bool checkforBipartite(int G[][V])
{
	int coloringarray[V];
		for (int i = 0; i < V; ++i)
		coloringarray[i] = -1;

	// Checking non colored vertices of graph
		for (int i = 0; i < V; i++)
			if (coloringarray[i] == -1)
			if (Bipartitefxn(G, i, coloringarray) == false)
				return false;

	return true;
}

//--------------------------------Function to check cliques-------------------------------------//
// We will returns true if graph can be divided into two Cliques, otherwise returns false.
bool TwoCliquespossible(int G[][V])
{
	// Find complement of the Graph
	// All values of graph are complemented except the diagonal value
		int GC[V][V];
		for (int i=0; i<V; i++)
		for (int j=0; j<V; j++)
		GC[i][j] = (i != j)? !G[i][j] : 0;
		
	return checkforBipartite(GC);
}

//--------------------------------Main Function-------------------------------------//
int main()
{
	    FAST;
		int G[][V] = {{0, 1, 1, 1, 0},
					  {1, 0, 1, 0, 0},
					  {1, 1, 0, 0, 0},
					  {0, 1, 0, 0, 1},
					  {0, 0, 0, 1, 0}
					  };


		TwoCliquespossible(G) ? cout << "Yes, it is possible" :
		cout << "No, it is not";
		return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Time Complexity ⏳

The time complexity of the above-discussed approach is O(V²). Here V is the vertices present in the graph.

Space Complexity 🌌

The space complexity of the above approach is O(1). As we are not using any extra spaces and each operation in the queue takes O(1) space. The space complexity is constant.