This slideshow introduces and explains the "Clique" Problem.
We start with some definitions and background.
A Clique is complete graph i.e. a graph where each node is connected to every other node by at least one edge.
Example of a clique:
A
B
C
D
E
F
If in a graph $G$ there exists a complete subgraph of $k$ nodes, $G$ is said to contain a $k$-clique.
For example, the following graph contains a $3$-clique. (Actually, there is more than one.)
1
2
3
4
5
6
Any clique with the largest number of vertices in a graph $G$ is called a Maximum Clique in $G$.
For example, the Maximum Clique in this graph is a $4$-clique.
The Clique Problem can be defined as either of the following:
Given a graph $G = (V , E)$, find the Maximum Clique in $G$. This is the optimization form of the problem.
Or
Given a graph $G = (V, E)$, and a number $k$, does $G$ contain a Clique of size $\geq k$ ? This is the decision form of the problem.
a
b
c
d
e
f
g
h
i
j
In the graph below does there exist a clique of size $\geq 5$?
No
In the graph below does there exist a clique of size $\geq 4$?
Yes
