Introduction

The Bron-Kerbosch algorithm is a recursive backtracking algorithm used for finding all maximal cliques—a subset of vertices in which every two distinct vertices are adjacent—in an undirected graph. Developed by Coen Bron and Joep Kerbosch in 1973, this algorithm has become one of the cornerstones in computational graph theory due to its efficiency and applicability in various domains like social network analysis, bioinformatics, and network topology.

Technical Explanation

A clique is defined as a subset of vertices of an undirected graph such that every two distinct vertices are connected by an edge. A maximal clique is a clique that cannot be extended by including one more adjacent vertex. The Bron-Kerbosch algorithm efficiently finds all maximal cliques in a graph using a recursive process and employs a pivoting strategy to minimize unnecessary recursive calls, enhancing its performance.

Properties

1. Input: An undirected graph represented either by adjacency lists or adjacency matrices.
2. Output: All maximal cliques in the given graph.
3. Time Complexity: The worst-case time complexity is $O(3^{n/3})$, where $n$ is the number of vertices, but it performs significantly faster on graphs with sparse connectivity.

Steps of the Algorithm

The Bron-Kerbosch algorithm involves the following steps:

1. Pivot Choice: Selecting a pivot vertex to reduce the number of recursive calls. The pivot minimizes branching and can be any vertex from the set of potential clique candidates.
2. Recursion: • A recursive call is made with the following parameters: • Current clique `R` (initially empty). • Potential candidates `P` (vertices that can be added to the current clique). • Excluded vertices `X` (vertices already processed in earlier steps). • The recursion progresses by adding one candidate vertex from `P` to `R` and updating `P` and `X` accordingly. • If `P` and `X` are both empty, `R` is a maximal clique, and it's yielded as a result.
3. Backtracking: The algorithm systematically backtracks by returning to previous states in the recursive stack to explore all potential cliques.

Pseudocode

• A: [B, C] • B: [A, D] • C: [A, D] • D: [B, C] • In the above graph, choosing `A` as a pivot reduces exploring `{B, C}` directly as a smaller independent recursion branch.