Editing Clique problem (section)

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