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.

---

Youtube Channel: https://shorturl.at/inryW