Greedy approach to find a single maximal clique in O(V^2) time complexity


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 (Θ(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.

single_maximal_clique

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(n2) (i.e. O(Edges)) time in the worst case.

Space Complexity

  • The greedy algoorithm takes O(n2) auxiliary space in the worst case.
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】

References