Maximal Clique Problem | Recursive Solution
Given a small graph with N nodes and E edges, the task is to find the maximum clique in the given graph. A clique is a complete subgraph of a given graph. This means that all nodes in the said subgraph are directly connected to each other, or there is an edge between any two nodes in the subgraph. The maximal clique is the complete subgraph of a given graph which contains the maximum number of nodes.
Examples:
Input: N = 4, edges[][] = {{1, 2}, {2, 3}, {3, 1}, {4, 3}, {4, 1}, {4, 2}}
Output: 4
Input: N = 5, edges[][] = {{1, 2}, {2, 3}, {3, 1}, {4, 3}, {4, 5}, {5, 3}}
Output: 3
Approach: The idea is to use recursion to solve the problem.
- When an edge is added to the present list, check that if by adding that edge to the present list, does it still form a clique or not.
- The vertices are added until the list does not form a clique. Then, the list is backtracked to find a larger subset which forms a clique.
Below is the implementation of the above approach:
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
// Stores the vertices
int store[MAX], n;
// Graph
int graph[MAX][MAX];
// Degree of the vertices
int d[MAX];
// Function to check if the given set of
// vertices in store array is a clique or not
bool is_clique(int b)
{
// Run a loop for all set of edges
for (int i = 1; i < b; i++) {
for (int j = i + 1; j < b; j++)
// If any edge is missing
if (graph[store[i]][store[j]] == 0)
return false;
}
return true;
}
// Function to find all the sizes
// of maximal cliques
int maxCliques(int i, int l)
{
// Maximal clique size
int max_ = 0;
// Check if any vertices from i+1
// can be inserted
for (int j = i + 1; j <= n; j++) {
// Add the vertex to store
store[l] = j;
// If the graph is not a clique of size k then
// it cannot be a clique by adding another edge
if (is_clique(l + 1)) {
// Update max
max_ = max(max_, l);
// Check if another edge can be added
max_ = max(max_, maxCliques(j, l + 1));
}
}
return max_;
}
// Driver code
int main()
{
int edges[][2] = { { 1, 2 }, { 2, 3 }, { 3, 1 },
{ 4, 3 }, { 4, 1 }, { 4, 2 } };
int size = sizeof(edges) / sizeof(edges[0]);
n = 4;
for (int i = 0; i < size; i++) {
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
d[edges[i][0]]++;
d[edges[i][1]]++;
}
cout << maxCliques(0, 1);
return 0;
}
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 100, n;
// Stores the vertices
static int []store = new int[MAX];
// Graph
static int [][]graph = new int[MAX][MAX];
// Degree of the vertices
static int []d = new int[MAX];
// Function to check if the given set of
// vertices in store array is a clique or not
static boolean is_clique(int b)
{
// Run a loop for all set of edges
for (int i = 1; i < b; i++)
{
for (int j = i + 1; j < b; j++)
// If any edge is missing
if (graph[store[i]][store[j]] == 0)
return false;
}
return true;
}
// Function to find all the sizes
// of maximal cliques
static int maxCliques(int i, int l)
{
// Maximal clique size
int max_ = 0;
// Check if any vertices from i+1
// can be inserted
for (int j = i + 1; j <= n; j++)
{
// Add the vertex to store
store[l] = j;
// If the graph is not a clique of size k then
// it cannot be a clique by adding another edge
if (is_clique(l + 1))
{
// Update max
max_ = Math.max(max_, l);
// Check if another edge can be added
max_ = Math.max(max_, maxCliques(j, l + 1));
}
}
return max_;
}
// Driver code
public static void main(String[] args)
{
int [][]edges = { { 1, 2 }, { 2, 3 }, { 3, 1 },
{ 4, 3 }, { 4, 1 }, { 4, 2 } };
int size = edges.length;
n = 4;
for (int i = 0; i < size; i++)
{
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
d[edges[i][0]]++;
d[edges[i][1]]++;
}
System.out.print(maxCliques(0, 1));
}
}
// This code is contributed by 29AjayKumar
# Python3 implementation of the approach
MAX = 100;
n = 0;
# Stores the vertices
store = [0] * MAX;
# Graph
graph = [[0 for i in range(MAX)] for j in range(MAX)];
# Degree of the vertices
d = [0] * MAX;
# Function to check if the given set of
# vertices in store array is a clique or not
def is_clique(b):
# Run a loop for all set of edges
for i in range(1, b):
for j in range(i + 1, b):
# If any edge is missing
if (graph[store[i]][store[j]] == 0):
return False;
return True;
# Function to find all the sizes
# of maximal cliques
def maxCliques(i, l):
# Maximal clique size
max_ = 0;
# Check if any vertices from i+1
# can be inserted
for j in range(i + 1, n + 1):
# Add the vertex to store
store[l] = j;
# If the graph is not a clique of size k then
# it cannot be a clique by adding another edge
if (is_clique(l + 1)):
# Update max
max_ = max(max_, l);
# Check if another edge can be added
max_ = max(max_, maxCliques(j, l + 1));
return max_;
# Driver code
if __name__ == '__main__':
edges = [[ 1, 2 ],[ 2, 3 ],[ 3, 1 ],
[ 4, 3 ],[ 4, 1 ],[ 4, 2 ]];
size = len(edges);
n = 4;
for i in range(size):
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
d[edges[i][0]] += 1;
d[edges[i][1]] += 1;
print(maxCliques(0, 1));
# This code is contributed by PrinciRaj1992
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 100, n;
// Stores the vertices
static int []store = new int[MAX];
// Graph
static int [,]graph = new int[MAX,MAX];
// Degree of the vertices
static int []d = new int[MAX];
// Function to check if the given set of
// vertices in store array is a clique or not
static bool is_clique(int b)
{
// Run a loop for all set of edges
for (int i = 1; i < b; i++)
{
for (int j = i + 1; j < b; j++)
// If any edge is missing
if (graph[store[i],store[j]] == 0)
return false;
}
return true;
}
// Function to find all the sizes
// of maximal cliques
static int maxCliques(int i, int l)
{
// Maximal clique size
int max_ = 0;
// Check if any vertices from i+1
// can be inserted
for (int j = i + 1; j <= n; j++)
{
// Add the vertex to store
store[l] = j;
// If the graph is not a clique of size k then
// it cannot be a clique by adding another edge
if (is_clique(l + 1))
{
// Update max
max_ = Math.Max(max_, l);
// Check if another edge can be added
max_ = Math.Max(max_, maxCliques(j, l + 1));
}
}
return max_;
}
// Driver code
public static void Main(String[] args)
{
int [,]edges = { { 1, 2 }, { 2, 3 }, { 3, 1 },
{ 4, 3 }, { 4, 1 }, { 4, 2 } };
int size = edges.GetLength(0);
n = 4;
for (int i = 0; i < size; i++)
{
graph[edges[i, 0], edges[i, 1]] = 1;
graph[edges[i, 1], edges[i, 0]] = 1;
d[edges[i, 0]]++;
d[edges[i, 1]]++;
}
Console.Write(maxCliques(0, 1));
}
}
// This code is contributed by PrinciRaj1992
<script>
// Javascript implementation of the approach
let MAX = 100, n;
// Stores the vertices
let store = new Array(MAX);
store.fill(0);
// Graph
let graph = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
graph[i] = new Array(MAX);
for(let j = 0; j < MAX; j++)
{
graph[i][j] = 0;
}
}
// Degree of the vertices
let d = new Array(MAX);
d.fill(0);
// Function to check if the given set of
// vertices in store array is a clique or not
function is_clique(b)
{
// Run a loop for all set of edges
for (let i = 1; i < b; i++)
{
for (let j = i + 1; j < b; j++)
// If any edge is missing
if (graph[store[i]][store[j]] == 0)
return false;
}
return true;
}
// Function to find all the sizes
// of maximal cliques
function maxCliques(i, l)
{
// Maximal clique size
let max_ = 0;
// Check if any vertices from i+1
// can be inserted
for (let j = i + 1; j <= n; j++)
{
// Add the vertex to store
store[l] = j;
// If the graph is not a clique of size k then
// it cannot be a clique by adding another edge
if (is_clique(l + 1))
{
// Update max
max_ = Math.max(max_, l);
// Check if another edge can be added
max_ = Math.max(max_, maxCliques(j, l + 1));
}
}
return max_;
}
let edges = [ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ],
[ 4, 3 ], [ 4, 1 ], [ 4, 2 ] ];
let size = edges.length;
n = 4;
for (let i = 0; i < size; i++)
{
graph[edges[i][0]][edges[i][1]] = 1;
graph[edges[i][1]][edges[i][0]] = 1;
d[edges[i][0]]++;
d[edges[i][1]]++;
}
document.write(maxCliques(0, 1));
// This code is contributed by suresh07.
</script>
Output
4
Time complexity: O(2^n * n^2)
The time complexity of this algorithm is O(2^n * n^2), where ‘n’ is the number of vertices in the graph. This is because ‘maxCliques’ is a recursive function that calculates all possible subsets of the vertices and calls ‘is_clique’ function to check if the given set of vertices form a clique or not. The ‘is_clique’ function takes O(n^2) time as it needs to check for all the edges in the graph.
Auxilary Space: O(n^2 + n)
The space complexity of this algorithm is O(n^2 + n), where ‘n’ is the number of vertices in the graph. This is because we need to store the graph in the form of an adjacency matrix which requires O(n^2) space. Apart from this, we need to store the vertices in ‘store’ array which takes O(n) space.
Bron-Kerbosch Algorithm for Maximal Cliques Detection
The Bron-Kerbosch algorithm is chosen for its efficiency and effectiveness in finding all maximal cliques in an undirected graph. This algorithm employs a recursive depth-first search mechanism, which avoids the redundancy and inefficiency inherent in other brute-force methods.
Follow the steps to solve the problem:
- Converts a list of edges to an adjacency list representation of the graph to facilitate quick access to neighbors.
- Initializes three sets: R (current clique), P (potential nodes that can be added to the clique), and X (nodes already processed and not included in the clique).
- Utilizes a recursive approach where for each node in P, the node is added to R, and the algorithm recursively explores further potential cliques.
- The recursion continues, refining P and X based on adjacency relations, until P and X are empty, indicating a maximal clique has been found.
- Outputs the maximal clique size after computing all possible cliques.
Below is the implementation of above approach:
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
void bronKerbosch(
unordered_set<int>&& R, unordered_set<int>&& P,
unordered_set<int>&& X,
unordered_map<int, unordered_set<int> >& graph,
vector<unordered_set<int> >& cliques)
{
if (P.empty() && X.empty()) {
cliques.push_back(R);
return;
}
while (!P.empty()) {
int v = *P.begin();
unordered_set<int> newR = R;
newR.insert(v);
unordered_set<int> newP;
for (int p : P) {
if (graph[v].find(p) != graph[v].end()) {
newP.insert(p);
}
}
unordered_set<int> newX;
for (int x : X) {
if (graph[v].find(x) != graph[v].end()) {
newX.insert(x);
}
}
bronKerbosch(move(newR), move(newP), move(newX),
graph, cliques);
P.erase(v);
X.insert(v);
}
}
int main()
{
vector<vector<int> > edges
= { { 1, 2 }, { 2, 3 }, { 3, 1 },
{ 4, 3 }, { 4, 1 }, { 4, 2 } };
int n = 4; // Number of nodes
// Create an adjacency list from the edges
unordered_map<int, unordered_set<int> > graph;
for (const auto& edge : edges) {
int u = edge[0];
int v = edge[1];
graph[u].insert(v);
graph[v].insert(u);
}
unordered_set<int> vertices;
for (const auto& pair : graph) {
vertices.insert(pair.first);
}
vector<unordered_set<int> > allCliques;
bronKerbosch({}, move(vertices), {}, graph, allCliques);
int maxCliqueSize = 0;
for (const auto& clique : allCliques) {
maxCliqueSize = max(
maxCliqueSize, static_cast<int>(clique.size()));
}
cout << maxCliqueSize << endl;
return 0;
}
import java.util.*;
public class BronKerbosch {
public static Set<Set<Integer> >
bronKerbosch(Set<Integer> R, Set<Integer> P,
Set<Integer> X,
Map<Integer, Set<Integer> > graph)
{
Set<Set<Integer> > cliques = new HashSet<>();
if (P.isEmpty() && X.isEmpty()) {
cliques.add(new HashSet<>(R));
}
while (!P.isEmpty()) {
int v = P.iterator().next();
Set<Integer> newR = new HashSet<>(R);
newR.add(v);
Set<Integer> newP = new HashSet<>(P);
newP.retainAll(graph.get(v));
Set<Integer> newX = new HashSet<>(X);
newX.retainAll(graph.get(v));
cliques.addAll(
bronKerbosch(newR, newP, newX, graph));
P.remove(v);
X.add(v);
}
return cliques;
}
public static void main(String[] args)
{
List<int[]> edges = Arrays.asList(
new int[] { 1, 2 }, new int[] { 2, 3 },
new int[] { 3, 1 }, new int[] { 4, 3 },
new int[] { 4, 1 }, new int[] { 4, 2 });
int n = 4; // Number of nodes
// Create an adjacency list from the edges
Map<Integer, Set<Integer> > graph = new HashMap<>();
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
graph.computeIfAbsent(u, k -> new HashSet<>())
.add(v);
graph.computeIfAbsent(v, k -> new HashSet<>())
.add(u);
}
Set<Integer> vertices
= new HashSet<>(graph.keySet());
Set<Set<Integer> > allCliques
= bronKerbosch(new HashSet<>(), vertices,
new HashSet<>(), graph);
int maxCliqueSize = allCliques.stream()
.mapToInt(Set::size)
.max()
.orElse(-1);
System.out.println(maxCliqueSize);
}
}
// This code is contributed by Shivam Gupta
def bron_kerbosch(R, P, X, graph):
if not P and not X:
yield R
while P:
v = P.pop()
yield from bron_kerbosch(
R.union({v}),
P.intersection(graph[v]),
X.intersection(graph[v]),
graph
)
X.add(v)
def main():
edges = [(1, 2), (2, 3), (3, 1), (4, 3), (4, 1), (4, 2)]
n = 4 # Number of nodes
# Create an adjacency list from the edges
graph = {i: set() for i in range(1, n + 1)}
for u, v in edges:
graph[u].add(v)
graph[v].add(u)
# Convert set keys into sorted lists for consistent ordering
graph = {key: set(graph[key]) for key in graph}
all_cliques = list(bron_kerbosch(set(), set(graph.keys()), set(), graph))
if all_cliques:
max_clique_size = max(len(clique) for clique in all_cliques)
else:
max_clique_size = -1
print(max_clique_size)
if __name__ == "__main__":
main()
function bronKerbosch(R, P, X, graph) {
let cliques = new Set();
if (P.size === 0 && X.size === 0) {
cliques.add(new Set(R));
}
for (let v of P) {
let newR = new Set(R);
newR.add(v);
let newP = new Set([...P].filter(x => graph.get(v).has(x)));
let newX = new Set([...X].filter(x => graph.get(v).has(x)));
cliques = new Set([...cliques, ...bronKerbosch(newR, newP, newX, graph)]);
P.delete(v);
X.add(v);
}
return cliques;
}
let edges = [
[1, 2], [2, 3], [3, 1],
[4, 3], [4, 1], [4, 2]
];
let n = 4; // Number of nodes
// Create an adjacency list from the edges
let graph = new Map();
for (let edge of edges) {
let [u, v] = edge;
graph.set(u, (graph.get(u) || new Set()).add(v));
graph.set(v, (graph.get(v) || new Set()).add(u));
}
let vertices = new Set(graph.keys());
let allCliques = bronKerbosch(new Set(), vertices, new Set(), graph);
let maxCliqueSize = Math.max(...Array.from(allCliques).map(set => set.size), -1);
console.log(maxCliqueSize);
Output
4
Time Complexity: O(3^(n/3))
Auxilary Space: O(n) for recursion stack depth, plus the space needed for sets R, P, and X.