Editing Clique problem (section)

===Finding maximum cliques in arbitrary graphs===
It is possible to find the maximum clique, or the clique number, of an arbitrary ''n''-vertex graph in time {{math|1={{italics correction|''O''}}(3<sup>''n''/3</sup>) = {{italics correction|''O''}}(1.4422<sup>''n''</sup>)}} by using one of the algorithms described above to list all maximal cliques in the graph and returning the largest one. However, for this variant of the clique problem better worst-case time bounds are possible. The algorithm of {{harvtxt|Tarjan|Trojanowski|1977}} solves this problem in time {{math|1={{italics correction|''O''}}(2<sup>''n''/3</sup>) = {{italics correction|''O''}}(1.2599<sup>''n''</sup>)}}. It is a recursive backtracking scheme similar to that of the [[Bron–Kerbosch algorithm]], but is able to eliminate some recursive calls when it can be shown that the cliques found within the call will be suboptimal. {{harvtxt|Jian|1986}} improved the time to {{math|1={{italics correction|''O''}}(2<sup>0.304''n''</sup>) = {{italics correction|''O''}}(1.2346<sup>''n''</sup>)}}, and {{harvtxt|Robson|1986}} improved it to {{math|1={{italics correction|''O''}}(2<sup>0.276''n''</sup>) = {{italics correction|''O''}}(1.2108<sup>''n''</sup>)}} time, at the expense of greater space usage. Robson's algorithm combines a similar backtracking scheme (with a more complicated case analysis) and a [[dynamic programming]] technique in which the optimal solution is precomputed for all small connected subgraphs of the [[complement graph]]. These partial solutions are used to shortcut the backtracking recursion. The fastest algorithm known today is a refined version of this method by {{harvtxt|Robson|2001}} which runs in time {{math|1={{italics correction|''O''}}(2<sup>0.249''n''</sup>) = {{italics correction|''O''}}(1.1888<sup>''n''</sup>)}}.{{sfnp|Robson|2001}}

There has also been extensive research on [[heuristic algorithm]]s for solving maximum clique problems without worst-case runtime guarantees, based on methods including [[branch and bound]],<ref>{{harvtxt|Balas|Yu|1986}}; {{harvtxt|Carraghan|Pardalos|1990}}; {{harvtxt|Pardalos|Rogers|1992}}; {{harvtxt|Östergård|2002}}; {{harvtxt|Fahle|2002}}; {{harvtxt|Tomita|Seki|2003}}; {{harvtxt|Tomita|Kameda|2007}}; {{harvtxt|Konc|Janežič|2007}}.</ref> [[Local search (optimization)|local search]],<ref>{{harvtxt|Battiti|Protasi|2001}}; {{harvtxt|Katayama|Hamamoto|Narihisa|2005}}.</ref> [[greedy algorithm]]s,<ref>{{harvtxt|Abello|Pardalos|Resende|1999}}; {{harvtxt|Grosso|Locatelli|Della Croce|2004}}.</ref> and [[constraint programming]].{{sfnp|Régin|2003}} Non-standard computing methodologies that have been suggested for finding cliques include [[DNA computing]]<ref>{{harvtxt|Ouyang|Kaplan|Liu|Libchaber|1997}}. Although the title refers to maximal cliques, the problem this paper solves is actually the maximum clique problem.</ref> and [[adiabatic quantum computation]].{{sfnp|Childs|Farhi|Goldstone|Gutmann|2002}} The maximum clique problem was the subject of an implementation challenge sponsored by [[DIMACS]] in 1992–1993,{{sfnp|Johnson|Trick|1996}} and a collection of graphs used as benchmarks for the challenge, which is publicly available.<ref>[http://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/ DIMACS challenge graphs for the clique problem] {{Webarchive|url=https://web.archive.org/web/20180330210743/http://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/ |date=2018-03-30 }}, accessed 2009-12-17.</ref>