Finds largest complete subgraph (all vertices connected)
Time: O(3ⁿ/³)
Space: O(V)
Use Case: Social network analysis, bioinformatics, data mining
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Maximal Clique
A clique is a set of vertices that are all pairwise connected. A maximal clique cannot be extended by adding another vertex, and finding all maximal cliques, or the single largest one, is a fundamental NP-hard problem in network analysis.
How it works
The Bron-Kerbosch algorithm enumerates all maximal cliques by recursive backtracking over three sets: the current clique R, candidates P that connect to all of R, and excluded vertices X already covered. Choosing a good pivot dramatically prunes the recursion, and processing vertices in degeneracy order gives the best known enumeration bound of O(3 to the power n/3), matching the maximum possible number of maximal cliques.
Applications
Clique detection finds tightly knit communities in social networks, protein interaction complexes in biology, correlated assets in finance, and co-purchased product groups in recommender systems. Clique problems are also the standard vehicle for teaching NP-completeness reductions.