Reading time: 40 minutes
A clique is a subset of vertices of an undirected graph G such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs.
A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. Maximal cliques can be very small. A graph may contain a non-maximal clique with many vertices and a separate clique of size 2 which is maximal. While a maximum (i.e., largest) clique is necessarily maximal, the converse does not hold.
There can be more than one single maximal clique in a non-complete graph (since complete graph is a maximal clique itself). To find a single maximal clique in a graph we use a straightforward greedy algorithm.
In greedy approach of finding a single maximal clique we start with any Starting with an arbitrary clique (for instance, any single vertex or even the empty set), grow the current clique one vertex at a time by looping through the graph's remaining vertices.
For each vertex v that this loop examines, add v to the clique if it is adjacent to every vertex that is already in the clique, and discard v otherwise. The maximal clique can be different if we start with differnet vertex as a graph may have more than one maximal clique.
- Start from an arbitrary vertex
- Given a clique of size, repeat:
- Add a vertex randomly from the common neighbors of the existing clique
- If there is no common neighbors, stop and return the clique
The above algorithm runs in linear time in the size of the graph (Θ(n2) edges) because of:
- the ease of finding maximal cliques
- their potential small size
Following is an example graph with 6 vertices and 4 different maximal cliques. On selection of different arbitrary start vertex we may get different maximal clique as output of the algorithm.
Code in Python3
from collections import defaultdict import random def find_single_clique(graph): clique =  vertices = list(graph.keys()) rand = random.randrange(0, len(vertices), 1) clique.append(vertices[rand]) for v in vertices: if v in clique: continue isNext = True for u in clique: if u in graph[v]: continue else: isNext = False break if isNext: clique.append(v) return sorted(clique) graph = dict() graph['A'] = ['B', 'C', 'E'] graph['B'] = ['A', 'C', 'D', 'F'] graph['C'] = ['A', 'B', 'D', 'F'] graph['D'] = ['C', 'E', 'B', 'F'] graph['E'] = ['A', 'D'] graph['F'] = ['B', 'C', 'D'] clique = find_single_clique(graph) print('A maximal clique in the graph is: ', clique)
A maximal clique in the graph is: ['B', 'C', 'D', 'F']
- The greedy algorithm takes O(n2) (i.e. O(Edges)) time in the worst case.
- The greedy algoorithm takes O(n2) auxiliary space in the worst case.