Editing Clique problem (section)

==History and applications==
The study of complete subgraphs in mathematics predates the "clique" terminology. For instance, complete subgraphs make an early appearance in the mathematical literature in the graph-theoretic reformulation of [[Ramsey theory]] by {{harvtxt|Erdős|Szekeres|1935}}. But the term "clique" and the problem of algorithmically listing cliques both come from the social sciences, where complete subgraphs are used to model [[clique|social cliques]], groups of people who all know each other. {{harvtxt|Luce|Perry|1949}} used graphs to model social networks, and adapted the social science terminology to graph theory. They were the first to call complete subgraphs "cliques". The first algorithm for solving the clique problem is that of {{harvtxt|Harary|Ross|1957}},<ref name="bbpp">{{harvtxt|Bomze|Budinich|Pardalos|Pelillo|1999}}; {{harvtxt|Gutin|2004}}.</ref> who were motivated by the sociological application. Social science researchers have also defined various other types of cliques and maximal cliques in social network, "cohesive subgroups" of people or actors in the network all of whom share one of several different kinds of connectivity relation. Many of these generalized notions of cliques can also be found by constructing an undirected graph whose edges represent related pairs of actors from the social network, and then applying an algorithm for the clique problem to this graph.{{sfnp|Wasserman|Faust|1994}}

Since the work of Harary and Ross, many others have devised algorithms for various versions of the clique problem.<ref name="bbpp"/> In the 1970s, researchers began studying these algorithms from the point of view of [[worst-case analysis]]. See, for instance, {{harvtxt|Tarjan|Trojanowski|1977}}, an early work on the worst-case complexity of the maximum clique problem. Also in the 1970s, beginning with the work of {{harvtxt|Cook|1971}} and {{harvtxt|Karp|1972}}, researchers began using the theory of [[NP-complete]]ness and related intractability results to provide a mathematical explanation for the perceived difficulty of the clique problem. In the 1990s, a breakthrough series of papers beginning with {{harvtxt|Feige|Goldwasser|Lovász|Safra|1991}} showed that (assuming [[P ≠ NP]]) it is not even possible to [[approximation algorithm|approximate]] the problem accurately and efficiently.

Clique-finding algorithms have been used in [[chemistry]], to find chemicals that match a target structure{{sfnp|Rhodes|Willett|Calvet|Dunbar|2003}} and to model [[Docking (molecular)|molecular docking]] and the binding sites of chemical reactions.{{sfnp|Kuhl|Crippen|Friesen|1983}} They can also be used to find similar structures within different molecules.<ref>{{harvtxt|National Research Council Committee on Mathematical Challenges from Computational Chemistry|1995}}. See in particular [https://books.google.com/books?id=YkArAAAAYAAJ&pg=PA35 pp.&nbsp;35–36].</ref> In these applications, one forms a graph in which each vertex represents a matched pair of atoms, one from each of two molecules. Two vertices are connected by an edge if the matches that they represent are compatible with each other. Being compatible may mean, for instance, that the distances between the atoms within the two molecules are approximately equal, to within some given tolerance. A clique in this graph represents a set of matched pairs of atoms in which all the matches are compatible with each other.<ref>{{harvtxt|Muegge|Rarey|2001}}. See in particular [https://books.google.com/books?id=luNYUUfBQb4C&pg=PA6 pp.&nbsp;6–7].</ref> A special case of this method is the use of the [[modular product of graphs]] to reduce the problem of finding the [[maximum common induced subgraph]] of two graphs to the problem of finding a maximum clique in their product.{{sfnp|Barrow|Burstall|1976}}

In [[automatic test pattern generation]], finding cliques can help to bound the size of a test set.{{sfnp|Hamzaoglu|Patel|1998}} In [[bioinformatics]], clique-finding algorithms have been used to infer [[evolutionary tree]]s,{{sfnp|Day|Sankoff|1986}} [[protein structure prediction|predict protein structures]],{{sfnp|Samudrala|Moult|1998}} and find closely interacting clusters of proteins.{{sfnp|Spirin|Mirny|2003}} Listing the cliques in a [[dependency graph]] is an important step in the analysis of certain random processes.{{sfnp|Frank|Strauss|1986}} In mathematics, [[Keller's conjecture]] on face-to-face tiling of [[hypercube]]s was disproved by {{harvtxt|Lagarias|Shor|1992}}, who used a clique-finding algorithm on an associated graph to find a counterexample.<ref>The Keller graph used by {{harvtxt|Lagarias|Shor|1992}} has 1048576 vertices and clique size 1024. They described a synthetic construction for the clique, but also used clique-finding algorithms on smaller graphs to help guide their search. {{harvtxt|Mackey|2002}} simplified the proof by finding a clique of size 256 in a 65536-vertex Keller graph.</ref>