In an undirected graph, a clique is a complete sub-graph of the given graph. Complete sub- graph means, all the vertices of this sub-graph is connected to all other vertices of this sub- graph.

The Max-Clique problem is the computational problem of finding maximum clique of the graph. Max clique is used in many real-world problems.

To find a maximum clique, one can systematically inspect all subsets, but this sort of brute- force search is too time-consuming for networks comprising more than a few dozen vertices. Algorithm: Max-Clique (G, n, k)

S := Φ

for i = 1 to k do

t := choice (1…n)

if t Є S then

return failure

S := S ∪ t

for all pairs (i, j) such that i Є S and j Є S and i ≠ j do

if (i, j) is not a edge of the graph then

return failure

return success

Analysis

Max-Clique problem is a non-deterministic algorithm. In this algorithm, first we try to determine a set of k distinct vertices and then we try to test whether these vertices form a complete graph.

There is no polynomial time deterministic algorithm to solve this problem. This problem is NP- Complete.