Clique Detection

A clique is a subset of vertices that are all pairwise connected. A maximal clique cannot be extended by adding another vertex without breaking the all-connected property.

Algorithm What it does

Algorithm	What it does
Bron-Kerbosch	Enumerates all maximal cliques using backtracking with pivoting. Worst-case O(3^(V/3)), but fast in practice on sparse graphs. The same header also exposes `bron_kerbosch_clique_number(g)`, which returns only the size of the largest clique.

Bron-Kerbosch

Enumerates all maximal cliques using backtracking with pivoting. Worst-case O(3^(V/3)), but fast in practice on sparse graphs. The same header also exposes bron_kerbosch_clique_number(g), which returns only the size of the largest clique.

Clique enumeration is NP-hard in general. Cliques and independent sets are dual under graph complementation (a clique in G is an independent set in the complement), so neither direction is inherently cheaper — both face the same worst-case complexity.

Edit this Page