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.
Non Deterministic Clique Problem
Graph G

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 :

// 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
      S ← S ∪ { v }

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


  • 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:

Leave a Reply

Your email address will not be published. Required fields are marked *