Clique problem
Approximation algorithms

Several authors have considered approximation algorithms 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.

Feige (2004) describes a polynomial time algorithm that finds a clique of size Ω((log n /log log n)) in any graph that has clique number Ω(n /log n) for any constant k. By using this algorithm when the clique number of a given input graph is between n /log n and n /log n, switching to a different algorithm of Boppana & Halldórsson (1992) for graphs with higher clique numbers, and choosing a two-vertex clique if both algorithms fail to find anything, Feige provides an approximation algorithm that finds a clique with a number of vertices within a factor of O(n (log log n) /log n) of the maximum. Although the approximation ratio of this algorithm is weak, it is the best known to date. The results on hardness of approximation described below suggest that there can be no approximation algorithm with an approximation ratio significantly less than linear.
length_constraints:number_sentences[12]