Editing Clique problem (section)

{{Short description|Task of computing complete subgraphs}}
{{good article}}

[[File:Brute force Clique algorithm.svg|thumb|upright=1.35|The [[Brute-force search|brute force algorithm]] finds a 4-clique in this 7-vertex graph (the complement of the 7-vertex [[path graph]]) by systematically checking all [[Combination|C]](7,4)&nbsp;=&nbsp;35 4-vertex subgraphs for completeness.]]

In [[computer science]], the '''clique problem''' is the computational problem of finding [[clique (graph theory)|clique]]s (subsets of vertices, all [[Adjacent (graph theory)|adjacent]] to each other, also called [[complete graph|complete]] [[Glossary of graph theory#Subgraphs|subgraphs]]) in a [[Graph (discrete mathematics)|graph]]. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a [[maximum clique]] (a clique with the largest possible number of vertices), finding a maximum weight clique in a weighted graph, listing all [[maximal clique]]s (cliques that cannot be enlarged), and solving the [[decision problem]] of testing whether a graph contains a clique larger than a given size.

The clique problem arises in the following real-world setting. Consider a [[social network]], where the graph's [[vertex (graph theory)|vertices]] represent people, and the graph's [[edge (graph theory)|edges]] represent mutual acquaintance. Then a clique represents a subset of people who all know each other, and algorithms for finding cliques can be used to discover these groups of mutual friends. Along with its applications in social networks, the clique problem also has many applications in [[bioinformatics]], and [[computational chemistry]].

Most versions of the clique problem are hard. The clique decision problem is [[NP-complete]] (one of [[Karp's 21 NP-complete problems]]). The problem of finding the maximum clique is both [[parameterized complexity|fixed-parameter intractable]] and [[hardness of approximation|hard to approximate]]. And, listing all maximal cliques may require [[exponential time]] as there exist graphs with exponentially many maximal cliques. Therefore, much of the theory about the clique problem is devoted to identifying special types of graphs that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation.

To find a maximum clique, one can systematically inspect all subsets, but this sort of [[brute-force search]] is too time-consuming to be practical for networks comprising more than a few dozen vertices.
Although no [[polynomial time]] algorithm is known for this problem, more efficient [[algorithm]]s than the brute-force search are known. For instance, the [[Bron–Kerbosch algorithm]] can be used to list all maximal cliques in worst-case optimal time, and it is also possible to list them in polynomial time per clique.