# Non Deterministic Clique Problem

Non Deterministic Clique Problem is a very interesting NP-complete problem in complexity theory. We can solve it either way: using a deterministic algorithm or a non-deterministic algorithm.

• A clique of graph G = (V, E) refers to the subgraph G’ of G such that an edge exists between each pair of vertices in G’.
• In other words, G’ is a clique of G if it is a complete subgraph of G.
• The Max clique problem is to find the largest subgraph in G. Number of vertices involved in a clique is called the size of the clique.

Clique and Max clique of G are:

• (1, 2) – Clique
• (2, 4) – Clique
• (1, 3) – Clique
• (3, 4, 5) – Max Clique
• (1, 2, 4, 3) – Not a clique
• If we want to find a clique of size M, the non-deterministic algorithm first chooses M distinct vertices from the set of vertices V non-deterministically and forms the set S of size M.
• If two vertices in S are the same then restart the procedure.
• Once S is known, the algorithm tests the membership of each pair of vertices in S to check if S is a clique or not.
• For each pair of vertex u, v ∈ S, if the edge (u, v) ∈ E then S forms a complete graph and a clique of size M is found.

## Non Deterministic Clique Problem – Algorithm

The nondeterministic algorithm for the clique problem is presented below :

Algorithm NON_DET_CLIQUE(G)
// Description : Find clique of size M of graph G using non-deterministic algorithm
// Input : Graph G = (V, E)
// Output : Success / Failure

// Guessing stage
S ← Φ
for i ← 1 to M do
// M is size of clique
v ← select (1, n)
if v ∈ S then
fail()
else
S ← S ∪ { v }
end
end

// Verification stage: Check if S is clique
for each pair (u, v) ∈ S and u ≠ v do
if the edge (u, v) ∉ E then
fail()
end
end
success( )

## Applications

• In the field of chemistry, algorithms are utilised most frequently in the process of locating chemicals that match a target structure, followed by the preparation of the docking of the molecule and then the binding sites of typical chemical reactions.
• Finding the number of cliques can also assist in limiting the size of a test case or set, which is another application for this technique that can be utilised in autonomous test pattern development.
• The clique algorithm is one that has been utilised in the field of bioinformatics. It has been utilised to build evolutionary trees, sometimes anticipating protein-type structures, and then discovering closely the interaction clusters that are contained within proteins.