Clique problem
Đăng, Long, Phong
Hanoi University of Science, VNU
May 2025
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 1 / 42
Table of Contents
1 Introduction
2 Algorithms
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 2 / 42
Table of Contents
1 Introduction
2 Algorithms
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 3 / 42
Introduction
The Clique Problem is one of the most fundamental NP-complete
problems in computational complexity theory, often serving as a textbook
example in graph theory and algorithm design. Studied since the 1970s, it
gained prominence when Richard Karp included it in his seminal 1972
paper "Reducibility Among Combinatorial Problems", which laid the
groundwork for NP-completeness proofs. The problem is regarded as a
"million-dollar problem" due to its connection to the P and NP question,
one of the Clay Millennium Prize challenges. It has appeared in science
fiction books and films as a symbol of computational complexity, notably
in Travelling Salesman (2012).
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 4 / 42
Applications
In social networks, cliques represent groups where every member is
connected, useful for detecting tightly-knit communities.
In bioinformatics, cliques in protein-protein interaction networks can
indicate functional protein complexes.
In computer vision, cliques help identify consistent feature
correspondences across images.
In timetabling and scheduling, cliques represent sets of non-conflicting
tasks that can be executed concurrently.
In fraud detection, large cliques in transaction graphs may signal
collusive behavior or suspicious coordination.
In machine learning, cliques appear in graphical models and are used
for probabilistic inference.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 5 / 42
Preliminaries
Graph Theory Basics
A graph G = (V , E ) consists of:
A set of vertices V
A set of edges E ⊆ {{u, v } | u, v ∈ V , u ̸= v }
The neighborhood of a vertex v : N(v ) = {u ∈ V | {u, v } ∈ E }
Degree of vertex v : d(v ) = |N(v )|
Clique Definitions
A clique is a subset of vertices C ⊆ V such that every pair of vertices
in C is connected by an edge.
A maximum clique is a clique of largest possible size in G .
The size of the maximum clique is denoted ω(G ).
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 6 / 42
Table of Contents
1 Introduction
2 Algorithms
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 7 / 42
Algorithm Idea: Branch and Bound
Objective: Find a clique of maximum size in a given graph G = (V , E ).
High-Level Strategy:
Use a Branch and Bound (B&B) framework to explore subsets of
vertices.
At each step:
Branch: Choose a vertex and explore two cases:
Include the vertex in the current clique
Exclude the vertex
Bound: Estimate an upper bound on the clique size from current state
Prune the search if the bound ≤ current best solution
Maintain current best (maximum) clique found so far.
Benefits:
Guarantees exact solution
Search space reduced significantly via bounding
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 8 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
First, we will consider a graph as shown above.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 9 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
The red node represents the root, while blue nodes are candidates.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 10 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Add the vertex with the highest degree to the initial set (i.e., the root
node).
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 11 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
We obtain a 3-degree clique and store it in best clique.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 12 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Return to root, then choose the unvisited vertex with maximum
degree. (Gray-colored vertices indicate visited nodes)
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 13 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Return to root, then choose the unvisited vertex with maximum
degree.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 14 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Candidate selection continues in descending degree order.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 15 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Backtrack one step and select the next candidate using the same
criteria as above.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 16 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
We obtain a 4-clique which replaces the current best clique, as it
constitutes a larger solution.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 17 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Backtrack and prune all vertices with degree smaller than the current
clique size.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 18 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
current clique size + remaining candidates ≤ best clique size: prune
branch
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 19 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Process root nodes by descending degree order.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 20 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Prune all verties with degree smaller than the curent best clique size.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 21 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Backtrack and process root nodes by decending degree order.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 22 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Backtrack and process root nodes by decending degree order.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 23 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
Prune all verties with degree smaller than the curent best clique size.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 24 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
current clique size + remaining candidates ≤ best clique size: prune
branch
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 25 / 42
Algorithm Idea: Branch and Bound
Algorithm Explanation
All valid vertices processed - final clique extracted.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 26 / 42
Pre-processing: Distance-based Graph Reduction
Idea: Reduce search space using vertex distances from a central
vertex.
Steps:
1 Let v be the vertex with the highest degree in G .
2 Compute shortest-path distances dist(u) from v to every other vertex
u.
3 Group vertices into distance classes:
D0 = {u | dist(u) = 0}, D1 = {u | dist(u) = 1}, . . .
Key Observation:
If |dist(u) − dist(u ′ )| ≥ 2, then u and u ′ cannot be in the same
clique.
Search Strategy:
For each i = 0 to max dist − 1:
Consider subgraph Gi induced by Di ∪ Di+1
Run maximum clique algorithm on Gi
Update best clique if a larger one is found
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 27 / 42
Pre-processing: Connected Components
Observation: The distance-based reduction strategy only works correctly
on connected graphs.
Step 1: Decompose the graph into connected components
Use BFS or DFS to find all connected components of G
Let G1 , G2 , . . . , Gk be the connected components
Step 2: Apply clique search independently
For each component Gi :
1 Choose vertex vi with highest degree in Gi
2 Compute distance layers from vi
3 Apply distance-based reduction and search as previously described
Keep track of the largest clique found across all components
Benefit: Ensures correctness and allows parallel or modular processing.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 28 / 42
Heuristic Maximum Clique Algorithm
Core Idea
Hybrid approach combining:
Greedy initialization (exploitation)
Randomized local search (exploration)
Key Features
Simple implementation
Balanced exploration/exploitation
Scalable to large graphs
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 29 / 42
Step 1: Greedy Initialization
1 Sort vertices by non-increasing degree:
deg(v1 ) ≥ deg(v2 ) ≥ · · · ≥ deg(vn )
2 Initialize clique with highest-degree vertex
3 Iteratively add adjacent vertices: [1] each vertex vi in sorted order vi
connects to all clique members Add vi to clique
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 30 / 42
Steps 2-3: Iterative Improvement
2 Destruction Phase:
Randomly remove 2 vertices from current clique
3 Reconstruction Phase:
Add vertices back in degree order
Maintain complete connectivity
Why This Works
Random removal avoids local optimal
Degree-based addition maintains quality
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 31 / 42
Steps 4-5: Update & Termination
4 Update Rule:
(
Cnew if |Cnew | > |Cbest |
Cbest =
Cbest otherwise
5 Termination:
After fixed iterations (e.g., 1000)
Or if no improvement for 20% of iterations
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 32 / 42
Algorithm Analysis
Complexity
Time: O(I × n2 )
I iterations
n2 edge checks per iteration
Space: O(n2 ) (adjacency matrix)
Parameters to Tune
Number of removed vertices (default: 2)
Iteration count
Early stopping threshold
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 33 / 42
Bounding Theorem: Clique and Coloring
Theorem (Clique–Coloring Bound)
For any simple graph G ,
ω(G ) ≤ χ(G ) ,
where
ω(G ) is the size of a maximum clique in G ,
χ(G ) is the chromatic number of G .
Proof Sketch.
In any proper coloring of G , vertices of a clique must all receive different
colors. Thus, if k = χ(G ) colors suffice for G , no clique can have size
larger than k.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 34 / 42
Branch and Bound with Coloring
Goal: Find a maximum clique in a graph using pruning to reduce the
search space.
Key Steps:
1 Sort all vertices in ascending order of degree.
2 Iterate through vertices in reverse order (highest degree first).
3 For each vertex v :
Initialize a clique C = {v }.
Define a candidate set P as the set of vertices adjacent to all vertices
in C .
Apply greedy coloring to P:
Adjacent vertices receive different colors.
The number of colors provides an upper bound.
If |C | + #colors ≤ size of current best clique, prune the branch.
Otherwise, recurse with each vertex in P, updating C and P.
4 Use backtracking to explore all feasible extensions.
Advantage: Efficient pruning using a fast upper bound via coloring.
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 35 / 42
Code
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 36 / 42
Code
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 37 / 42
Code
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 38 / 42
Code
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 39 / 42
Code
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 40 / 42
Results
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 41 / 42
Results
Đăng, Long, Phong (VNU-HUS) Clique problem May 2025 42 / 42
