On the approximability of clique and related maximization problems

We consider approximations of the form n(1-o(1)) for the Maximum Clique problem, where n is the number of vertices in the input graph and where the "o(1)" term goes to zero as n increases. We show that sufficiently strong negative results for such problems, which we call strong inapproximability results, have interesting consequences for exact computation. A simple sampling method underlies most of our results. (C) 2003 Published by Elsevier Inc.