Editing Clique problem (section)

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