Editing Clique problem (section)

===Special classes of graphs===
[[File:Permutation graph.svg|thumb|In this [[permutation graph]], the maximum cliques correspond to the [[Longest increasing subsequence|longest decreasing subsequences]] (4,3,1) and (4,3,2) of the defining permutation.]]
[[Planar graph]]s, and other families of sparse graphs, have been discussed above: they have linearly many maximal cliques, of bounded size, that can be listed in linear time.<ref name="CN85"/> In particular, for planar graphs, any clique can have at most four vertices, by [[Kuratowski's theorem]].<ref name="planar"/>

[[Perfect graph]]s are defined by the properties that their clique number equals their [[chromatic number]], and that this equality holds also in each of their [[induced subgraph]]s. For perfect graphs, it is possible to find a maximum clique in polynomial time, using an algorithm based on [[semidefinite programming]].{{sfnp|Grötschel|Lovász|Schrijver|1988}}
However, this method is complex and non-combinatorial, and specialized clique-finding algorithms have been developed for many subclasses of perfect graphs.{{sfnp|Golumbic|1980}} In the [[complement graph]]s of [[bipartite graph]]s, [[Kőnig's theorem (graph theory)|Kőnig's theorem]] allows the maximum clique problem to be solved using techniques for [[Matching (graph theory)|matching]]. In another class of perfect graphs, the [[permutation graph]]s, a maximum clique is a [[Longest increasing subsequence|longest decreasing subsequence]] of the permutation defining the graph and can be found using known algorithms for the longest decreasing subsequence problem. Conversely, every instance of the longest decreasing subsequence problem can be described equivalently as a problem of finding a maximum clique in a permutation graph.<ref>{{harvtxt|Golumbic|1980}}, p. 159.</ref> {{harvtxt|Even|Pnueli|Lempel|1972}} provide an alternative quadratic-time algorithm for maximum cliques in [[comparability graph]]s, a broader class of perfect graphs that includes the permutation graphs as a special case.{{sfnp|Even|Pnueli|Lempel|1972}} In [[chordal graph]]s, the maximal cliques can be found by listing the vertices in an elimination ordering, and checking the clique [[neighborhood (graph theory)|neighborhoods]] of each vertex in this ordering.<ref>{{harvtxt|Blair|Peyton|1993}}, Lemma 4.5, p.&nbsp;19.</ref>

In some cases, these algorithms can be extended to other, non-perfect, classes of graphs as well. For instance, in a [[circle graph]], the neighborhood of each vertex is a permutation graph, so a maximum clique in a circle graph can be found by applying the permutation graph algorithm to each neighborhood.<ref>{{harvtxt|Gavril|1973}}; {{harvtxt|Golumbic|1980}}, p. 247.</ref> Similarly, in a [[unit disk graph]] (with a known geometric representation), there is a polynomial time algorithm for maximum cliques based on applying the algorithm for complements of bipartite graphs to shared neighborhoods of pairs of vertices.{{sfnp|Clark|Colbourn|Johnson|1990}}

[[File:Planted clique 15,32.svg|thumb|A random graph with a [[planted clique]]]]
The algorithmic problem of finding a maximum clique in a [[random graph]] drawn from the [[Erdős–Rényi model]] (in which each edge appears with probability {{math|1/2}}, independently from the other edges) was suggested by {{harvtxt|Karp|1976}}. Because the maximum clique in a random graph has logarithmic size with high probability, it
can be found by a brute force search in expected time {{math|2<sup>{{italics correction|''O''}}(log<sup>2</sup>''n'')</sup>}}. This is a [[quasi-polynomial time]] bound.{{sfnp|Song|2015}} Although the clique number of such graphs is usually very close to {{math|2&nbsp;log<sub>2</sub>''n''}}, simple [[greedy algorithm]]s as well as more sophisticated randomized approximation techniques only find cliques with size {{math|log<sub>2</sub>''n''}}, half as big. The number of maximal cliques in such graphs is with high probability exponential in {{math|log<sup>2</sup>''n''}}, which prevents methods that list all maximal cliques from running in polynomial time.{{sfnp|Jerrum|1992}} Because of the difficulty of this problem, several authors have investigated the [[planted clique]] problem, the clique problem on random graphs that have been augmented by adding large cliques.<ref>{{harvtxt|Arora|Barak|2009}}, Example 18.2, pp.&nbsp;362–363.</ref> While [[Spectral graph theory|spectral methods]]{{sfnp|Alon|Krivelevich|Sudakov|1998}} and [[semidefinite programming]]{{sfnp|Feige|Krauthgamer|2000}} can detect hidden cliques of size {{math|Ω({{radic|''n''}})}}, no polynomial-time algorithms are currently known to detect those of size {{math|''o''({{radic|''n''}})}} (expressed using [[Big O notation#Little-o notation|little-o notation]]).{{sfnp|Meka|Potechin|Wigderson|2015}}