Clique problem
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 O (3) = O (1.4422) 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 Tarjan & Trojanowski (1977) solves this problem in time O (2) = O (1.2599). 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. Jian (1986) improved the time to O (2) = O (1.2346), and Robson (1986) improved it to O (2) = O (1.2108) 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 Robson (2001) which runs in time O (2) = O (1.1888).

There has also been extensive research on heuristic algorithms for solving maximum clique problems without worst-case runtime guarantees, based on methods including branch and bound, local search, greedy algorithms, and constraint programming. Non-standard computing methodologies that have been suggested for finding cliques include DNA computing and adiabatic quantum computation. The maximum clique problem was the subject of an implementation challenge sponsored by DIMACS in 1992–1993, and a collection of graphs used as benchmarks for the challenge, which is publicly available.
detectable_format:title, length_constraints:number_paragraphs[3]