to every vertex that is already in the clique, and discard otherwise. This algorithm runs in linear time. 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 algorithms has studied the problem of finding a maximal clique. In particular, the problem of finding the lexicographically first maximal clique (the one found by the algorithm above) has been shown to be complete for the class of polynomial-time functions. This result implies that the problem is unlikely to be solvable within the parallel complexity class NC. Cliques of fixed size One can test whether a graph contains a -vertex clique, and find any such clique that it contains, using a brute force algorithm. This algorithm examines each subgraph with vertices and checks to see whether it forms a clique. It takes time , as expressed using big O notation. This is because there are subgraphs to check, each of which has edges whose presence in needs to be checked. Thus, the problem may be solved in polynomial time whenever is a fixed constant. However, when does not have a fixed value, but instead may vary as part of the input to the problem, the time is exponential. 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. In a graph with edges, there may be at most triangles (using big theta notation to indicate that this bound is tight). The worst case for this formula occurs when is itself a clique. Therefore, algorithms for listing all triangles must take at least time in the worst case (using big omega notation), and algorithms are known that match this time bound. For instance, describe an algorithm that sorts the vertices in order from highest degree to lowest and then iterates through each vertex in the sorted list, looking for triangles that include and do not include any previous vertex in the list. To do so the algorithm marks all neighbors of , searches through all edges incident to a neighbor of outputting a triangle for every edge that has two marked endpoints, and then removes the marks and deletes from the graph. As the authors show, the time for this algorithm is proportional