yog/properties/clique
Clique finding algorithms using the Bron-Kerbosch algorithm.
A clique is a subset of nodes where every pair of nodes is connected by an edge. Cliques represent tightly-knit communities or fully-connected subgraphs.
Algorithms
| Problem | Algorithm | Function | Complexity |
|---|---|---|---|
| Maximum clique | Bron-Kerbosch with pivot | max_clique/1 | O(3^(n/3)) |
| All maximal cliques | Bron-Kerbosch | all_maximal_cliques/1 | O(3^(n/3)) |
| k-Cliques | Bron-Kerbosch with pruning | k_cliques/2 | O(3^(n/3)) |
Key Concepts
- Clique: Complete subgraph - every pair of vertices is adjacent
- Maximal Clique: Cannot be extended by adding another vertex
- Maximum Clique: Largest clique in the graph (NP-hard to find)
- Clique Number: Size of the maximum clique, denoted ω(G)
- Clique Cover: Partition of vertices into cliques
The Bron-Kerbosch Algorithm
A backtracking algorithm that recursively explores potential cliques using three sets:
- R: Current clique being built
- P: Candidates that can extend R (connected to all in R)
- X: Excluded vertices (already processed)
Pivoting optimization: Choose a pivot vertex to reduce recursive calls, achieving the worst-case optimal O(3^(n/3)) bound.
Complexity Notes
Finding the maximum clique is NP-hard. The O(3^(n/3)) bound is tight - there exist graphs with exactly 3^(n/3) maximal cliques (Moon-Moser graphs).
Related Problems
- Independent Set: Clique in the complement graph
- Vertex Cover: Related via complement to independent set
- Graph Coloring: Lower bounded by clique number
Use Cases
- Social network analysis: Finding tightly-knit friend groups
- Bioinformatics: Protein interaction clusters
- Finance: Detecting collusion rings in trading
- Recommendation: Finding groups with similar preferences
- Compiler optimization: Register allocation (interference graphs)
References
- Wikipedia: Clique
- Wikipedia: Bron-Kerbosch Algorithm
- Moon-Moser Theorem (Clique Enumeration)
- CP-Algorithms: Finding Cliques
Values
pub fn all_maximal_cliques(
graph: model.Graph(n, e),
) -> List(set.Set(Int))Finds all maximal cliques in an undirected graph.
A maximal clique is a clique that cannot be extended by adding another node.
Time Complexity: O(3^(n/3)) worst case
Example
clique.all_maximal_cliques(graph)
// => [set.from_list([1, 2]), set.from_list([2, 3])]
pub fn k_cliques(
graph: model.Graph(n, e),
k: Int,
) -> List(set.Set(Int))Finds all cliques of exactly size k in an undirected graph.
Uses a modified Bron-Kerbosch algorithm with early pruning.
Time Complexity: O(3^(n/3)) worst case
Example
clique.k_cliques(graph, 3)
// => [set.from_list([1, 2, 3])]
pub fn max_clique(graph: model.Graph(n, e)) -> set.Set(Int)Finds the maximum clique in an undirected graph.
Returns the largest subset of nodes where every pair is connected.
Time Complexity: O(3^(n/3)) worst case
Example
clique.max_clique(graph)
// => set.from_list([1, 2, 3, 4])