Clique Decision Problem

Definition:

In the field of computer science, the clique decision problem is a kind of computation problem for finding the cliques or the subsets of the vertices which when all of them are adjacent to each other are also called complete subgraphs.

The clique decision problem has many formulations based on which the cliques and about the cliques the information should be found. There are some common formulations based on which the cliques are based such as finding the maximum clique, finding the maximum weight of the clique in a weighted graph, then listing all the maximum or maximal cliques, and finally solving the problem based on the decision of testing whether the graph has the larger cliques than that of the given size.

Maximum clique: a particular clique that has the largest possible number of vertices.

Maximal cliques: the cliques which further cannot be enlarged.

Applications of Clique decision problems :

1.       Clique decision finding problems algorithms are most abundantly used in chemistry to find the chemicals which have a match with a target structure and then to prepare the docking of the molecule and then the binding sites of common chemical reactions. They might be used to gather the information to find similar structures inside some different molecule. Hence, in these kinds of applications, a graph is formed where every vertex represents a pair that has a match with the pair of atoms one from each of the two molecules. So, two vertices are then connected by an edge if the match they represent is compatible with each other. Therefore, a clique in this particular graph denotes the set of a matched number of pairs of atoms in which all the matched elements are compatible with each other. Several special methods could have also been used such as the modular product of graphs, which can be used to reduce the problem of finding the maximum common induced sub graph in between two graphs to the problem of finding the maximum clique for their product.
2. It can also be used in automatic test pattern generation, where finding the number of cliques can also help to bound the size of a test case or set.
3. Used in bioinformatics, the clique algorithm has been used to achieve evolutionary trees, sometimes predicting protein type structures and then finding closely the interacting clusters inside proteins.

Consider an algorithm to find the maximum clique as follows :

When S = NULL.
for i = 1 till k then start do-while loop. 
t : = ch(1 to n)
if t belongs to S then
return fail.
When S:= S union t
Then for all pairs of I and j such that when i belongs to S and j belongs to S  and if i not equal to j then start do-while loop. 
And check if I and j is not an edge of that given graph then
Return fail.
Else return a true value.

Conclusion :

Thus, a clique is actually a complete total subgraph of a given particular graph and the max clique association problem is basically a computational problem for finding the maximum clique of the graph.

Reference

Clique Decision Problem