Editing Clique problem (section)

==Algorithms==

===Finding a single maximal clique===
A [[maximal element|maximal]] clique, sometimes called inclusion-maximal, is a clique that is not included in a larger clique.  Therefore, every clique is contained in a maximal clique.<ref>See, e.g., {{harvtxt|Frank|Strauss|1986}}.</ref> Maximal cliques can be very small.  A graph may contain a non-maximal clique with many vertices and a separate clique of size 2 which is maximal.  While a maximum (i.e., largest) clique is necessarily maximal, the converse does not hold.  There are some types of graphs in which every maximal clique is maximum; these are the [[complement (graph theory)|complements]] of the [[well-covered graph]]s, in which every maximal independent set is maximum.{{sfnp|Plummer|1993}} However, other graphs have maximal cliques that are not maximum.

A single maximal clique can be found by a straightforward [[greedy algorithm]]. Starting with an arbitrary clique (for instance, any single vertex or even the empty set), grow the current clique one vertex at a time by looping through the graph's remaining vertices. For each vertex {{mvar|v}} that this loop examines, add {{mvar|v}} to the clique if it is adjacent to every vertex that is already in the clique, and discard {{mvar|v}} otherwise. This algorithm runs in [[linear time]].<ref>{{harvtxt|Skiena|2009}}, [https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA526 p.&nbsp;526].</ref>  Because of the ease of finding maximal cliques, and their potential small size,  more attention has been given to the much harder algorithmic problem of finding a maximum or otherwise large clique. However, some research in [[parallel algorithm]]s has studied the problem of finding a maximal clique. In particular, the problem of finding the [[lexicographic ordering|lexicographically first]] maximal clique (the one found by the algorithm above) has been shown to be [[Complete (complexity)|complete]] for [[FP (complexity)|the class of polynomial-time functions]]. This result implies that the problem is unlikely to be solvable within the parallel complexity class [[NC (complexity)|NC]].{{sfnp|Cook|1985}}

===Cliques of fixed size===
One can test whether a graph {{mvar|G}} contains a {{mvar|k}}-vertex clique, and find any such clique that it contains, using a [[brute-force search|brute force algorithm]]. This algorithm examines each subgraph with {{mvar|k}} vertices and checks to see whether it forms a clique. It takes time {{math|{{italics correction|''O''}}(''n''<sup>''k''</sup>&nbsp;''k''<sup>2</sup>)}}, as expressed using [[big O notation]].
This is because there are {{math|{{italics correction|''O''}}(''n''<sup>''k''</sup>)}} subgraphs to check, each of which has {{math|{{italics correction|''O''}}(''k''<sup>2</sup>)}} edges whose presence in {{mvar|G}} needs to be checked. Thus, the problem may be solved in [[polynomial time]] whenever {{mvar|k}} is a fixed constant. However, when {{mvar|k}} does not have a fixed value, but instead may vary as part of the input to the problem, the time is exponential.<ref>E.g., see {{harvtxt|Downey|Fellows|1995}}.</ref>

The simplest nontrivial case of the clique-finding problem is finding a triangle in a graph, or equivalently determining whether the graph is [[triangle-free graph|triangle-free]].
In a graph {{mvar|G}} with {{mvar|m}} edges, there may be at most {{math|Θ(''m''<sup>3/2</sup>)}} triangles (using [[big theta notation]] to indicate that this bound is tight). The worst case for this formula occurs when {{mvar|G}} is itself a clique. Therefore, algorithms for listing all triangles must take at least {{math|Ω(''m''<sup>3/2</sup>)}} time in the worst case (using [[big omega notation]]), and algorithms are known that match this time bound.<ref>{{harvtxt|Itai|Rodeh|1978}} provide an algorithm with {{math|{{italics correction|''O''}}(''m''<sup>3/2</sup>)}} running time that finds a triangle if one exists but does not list all triangles; {{harvtxt|Chiba|Nishizeki|1985}} list all triangles in time {{math|{{italics correction|''O''}}(''m''<sup>3/2</sup>)}}.</ref> For instance, {{harvtxt|Chiba|Nishizeki|1985}} describe an algorithm that sorts the vertices in order from highest degree to lowest and then iterates through each vertex {{mvar|v}} in the sorted list, looking for triangles that include {{mvar|v}} and do not include any previous vertex in the list. To do so the algorithm marks all neighbors of {{mvar|v}}, searches through all edges incident to a neighbor of {{mvar|v}} outputting a triangle for every edge that has two marked endpoints, and then removes the marks and deletes {{mvar|v}} from the graph. As the authors show, the time for this algorithm is proportional to the [[arboricity]] of the graph (denoted {{math|''a''(''G'')}}) multiplied by the number of edges, which is {{math|{{italics correction|''O''}}(''m''&nbsp;''a''(''G''))}}. Since the arboricity is at most {{math|{{italics correction|''O''}}(''m''<sup>1/2</sup>)}}, this algorithm runs in time {{math|{{italics correction|''O''}}(''m''<sup>3/2</sup>)}}. More generally, all {{mvar|k}}-vertex cliques can be listed by a similar algorithm that takes time proportional to the number of edges multiplied by the arboricity to the power {{math|(''k''&nbsp;&minus;&nbsp;2)}}. For graphs of constant arboricity, such as planar graphs (or in general graphs from any non-trivial [[minor-closed graph family]]), this algorithm takes {{math|{{italics correction|''O''}}(''m'')}} time, which is optimal since it is linear in the size of the input.<ref name="CN85">{{harvtxt|Chiba|Nishizeki|1985}}.</ref>

If one desires only a single triangle, or an assurance that the graph is triangle-free, faster algorithms are possible. As {{harvtxt|Itai|Rodeh|1978}} observe, the graph contains a triangle if and only if its [[adjacency matrix]] and the square of the adjacency matrix contain nonzero entries in the same cell. Therefore, [[Computational complexity of matrix multiplication|fast matrix multiplication]] techniques can be applied to find triangles in time {{math|{{italics correction|''O''}}(''n''<sup>2.376</sup>)}}. {{harvtxt|Alon|Yuster|Zwick|1994}} used fast matrix multiplication to improve the {{math|{{italics correction|''O''}}(''m''<sup>3/2</sup>)}} algorithm for finding triangles to {{math|{{italics correction|''O''}}(''m''<sup>1.41</sup>)}}. These algorithms based on fast matrix multiplication have also been extended to problems of finding {{mvar|k}}-cliques for larger values of {{mvar|k}}.<ref>{{harvtxt|Eisenbrand|Grandoni|2004}}; {{harvtxt|Kloks|Kratsch|Müller|2000}}; {{harvtxt|Nešetřil|Poljak|1985}}; {{harvtxt|Vassilevska|Williams|2009}}; {{harvtxt|Yuster|2006}}.</ref>

===Listing all maximal cliques===
By a result of {{harvtxt|Moon|Moser|1965}}, every {{mvar|n}}-vertex graph has at most {{math|3<sup>''n''/3</sup>}} maximal cliques. They can be listed by the [[Bron–Kerbosch algorithm]], a recursive [[backtracking]] procedure of {{harvtxt|Bron|Kerbosch|1973}}. The main recursive subroutine of this procedure has three arguments: a partially constructed (non-maximal) clique, a set of candidate vertices that could be added to the clique, and another set of vertices that should not be added (because doing so would lead to a clique that has already been found). The algorithm tries adding the candidate vertices one by one to the partial clique, making a recursive call for each one. After trying each of these vertices, it moves it to the set of vertices that should not be added again. Variants of this algorithm can be shown to have worst-case running time {{math|{{italics correction|''O''}}(3<sup>''n''/3</sup>)}}, matching the number of cliques that might need to be listed.{{sfnp|Tomita|Tanaka|Takahashi|2006}} Therefore, this provides a worst-case-optimal solution to the problem of listing all maximal cliques. Further, the Bron–Kerbosch algorithm has been widely reported as being faster in practice than its alternatives.<ref>{{harvtxt|Cazals|Karande|2008}}; {{harvtxt|Eppstein|Löffler|Strash|2013}}.</ref>

However, when the number of cliques is significantly smaller than its worst case, other algorithms might be preferable. As {{harvtxt|Tsukiyama|Ide|Ariyoshi|Shirakawa|1977}} showed, it is also possible to list all maximal cliques in a graph in an amount of time that is polynomial per generated clique. An algorithm such as theirs in which the running time depends on the output size is known as an [[output-sensitive algorithm]]. Their algorithm is based on the following two observations, relating the maximal cliques of the given graph {{mvar|G}} to the maximal cliques of a graph {{math|''G''&nbsp;\&nbsp;''v''}} formed by removing an arbitrary vertex {{mvar|v}} from {{mvar|G}}:
*For every maximal clique {{mvar|K}} of {{math|''G''&nbsp;\&nbsp;''v''}}, either {{mvar|K}} continues to form a maximal clique in {{mvar|G}}, or {{math|''K''&nbsp;⋃&nbsp;{''v''} }} forms a maximal clique in {{mvar|G}}. Therefore, {{mvar|G}} has at least as many maximal cliques as {{math|''G''&nbsp;\&nbsp;''v''}} does.
*Each maximal clique in {{mvar|G}} that does not contain {{mvar|v}} is a maximal clique in {{math|''G''&nbsp;\&nbsp;''v''}}, and each maximal clique in {{mvar|G}} that does contain {{mvar|v}} can be formed from a maximal clique {{mvar|K}} in {{math|''G''&nbsp;\&nbsp;''v''}} by adding {{mvar|v}} and removing the non-neighbors of {{mvar|v}} from {{mvar|K}}.
Using these observations they can generate all maximal cliques in {{mvar|G}} by a recursive algorithm that chooses a vertex {{mvar|v}} arbitrarily and then, for each maximal clique {{mvar|K}} in {{math|''G''&nbsp;\&nbsp;''v''}}, outputs both {{mvar|K}} and the clique formed by adding {{mvar|v}} to {{mvar|K}} and removing the non-neighbors of {{mvar|v}}. However, some cliques of {{mvar|G}} may be generated in this way from more than one parent clique of {{math|''G''&nbsp;\&nbsp;''v''}}, so they eliminate duplicates by outputting a clique in {{mvar|G}} only when its parent in {{math|''G''&nbsp;\&nbsp;''v''}} is lexicographically maximum among all possible parent cliques. On the basis of this principle, they show that all maximal cliques in {{mvar|G}} may be generated in time {{math|{{italics correction|''O''}}(''mn'')}} per clique, where {{mvar|m}} is the number of edges in {{mvar|G}} and {{mvar|n}} is the number of vertices. {{harvtxt|Chiba|Nishizeki|1985}} improve this to {{math|O(''ma'')}} per clique, where {{mvar|a}} is the arboricity of the given graph. {{harvtxt|Makino|Uno|2004}} provide an alternative output-sensitive algorithm based on fast matrix multiplication. {{harvtxt|Johnson|Yannakakis|1988}} show that it is even possible to list all maximal cliques in [[lexicographic order]] with [[polynomial delay]] per clique. However, the choice of ordering is important for the efficiency of this algorithm: for the reverse of this order,
there is no polynomial-delay algorithm unless [[P = NP]].

On the basis of this result, it is possible to list all maximal cliques in polynomial time, for families of graphs in which the number of cliques is polynomially bounded. These families include [[chordal graph]]s, [[complete graph]]s, [[triangle-free graph]]s, [[interval graph]]s, graphs of bounded [[boxicity]], and [[planar graph]]s.{{sfnp|Rosgen|Stewart|2007}} In particular, the planar graphs have {{math|{{italics correction|''O''}}(''n'')}} cliques, of at most constant size, that can be listed in linear time. The same is true for any family of graphs that is both [[dense graph|sparse]] (having a number of edges at most a constant times the number of vertices) and [[Closure (mathematics)|closed]] under the operation of taking subgraphs.<ref name="CN85"/><ref name="ELS10"/>

===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>

===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}}

===Approximation algorithms===
Several authors have considered [[approximation algorithm]]s that attempt to find a clique or independent set that, although not maximum, has size as close to the maximum as can be found in polynomial time. Although much of this work has focused on independent sets in sparse graphs, a case that does not make sense for the complementary clique problem, there has also been work on approximation algorithms that do not use such sparsity assumptions.<ref>{{harvtxt|Boppana|Halldórsson|1992}}; {{harvtxt|Feige|2004}}; {{harvtxt|Halldórsson|2000}}.</ref>

{{harvtxt|Feige|2004}} describes a polynomial time algorithm that finds a clique of size {{math|Ω((log&nbsp;''n''/log&nbsp;log&nbsp;''n'')<sup>2</sup>)}} in any graph that has clique number {{math|Ω(''n''/log<sup>''k''</sup>''n'')}} for any constant {{mvar|k}}. By using this algorithm when the clique number of a given input graph is between {{math|''n''/log&nbsp;''n''}} and {{math|''n''/log<sup>3</sup>''n''}}, switching to a different algorithm of {{harvtxt|Boppana|Halldórsson|1992}} for graphs with higher clique numbers, and choosing a two-vertex clique if both algorithms fail to find anything, [[Uriel Feige|Feige]] provides an approximation algorithm that finds a clique with a number of vertices within a factor of {{math|O(''n''(log&nbsp;log&nbsp;''n'')<sup>2</sup>/log<sup>3</sup>''n'')}} of the maximum. Although the [[approximation ratio]] of this algorithm is weak, it is the best known to date.<ref>{{harvtxt|Liu|Lu|Yang|Xiao|2015}}: "In terms of the number of vertices in graphs, Feige shows the currently known best approximation ratio". Liu et al. are writing about the [[maximum independent set]] but for purposes of approximation there is no difference between the two problems.</ref> The results on [[hardness of approximation]] described below suggest that there can be no approximation algorithm with an approximation ratio significantly less than linear.