Get this book -> Problems on Array: For Interviews and Competitive Programming

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

# 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** (Ξ(n^{2}) 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.

# Implementation

**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)
```

**Output**

```
A maximal clique in the graph is: ['B', 'C', 'D', 'F']
```

# Complexity

**Time Complexity**

- The greedy algorithm takes O(n
^{2}) (i.e. O(Edges)) time in the worst case.

**Space Complexity**

- The greedy algoorithm takes O(n
^{2}) auxiliary space in the worst case.

## Related articles

Using Bron Kerbosch algorithm to find maximal cliques in O(3^(N/3))Algorithm to find cliques of a given size k γO(n^k) time complexityγ