Approximating Maximum Clique by Removing Subgraphs
Uriel Feige · SIAM Journal on Discrete Mathematics · 2004
We show an algorithm that finds cliques of size (log n/log log n) 2 whenever a graph has a clique of size at least n/(log n) b for an arbitrary constant b. This leads to an algorithm that approximates max clique within a factor of O(n(log log n) 2 /(log n) 3 ), which matches the best approximation ratio known for the chromatic number. The previously best approximation ratio known for max clique was O(n/(log n) 2 ).