Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set

We give a deterministic quasi-polynomial-time algorithm for the maximum independent set problem. If an N-vertex graph contains an independent set of size 2⁻ᵗN, where t is an integer with 1≤ t≤√log N/12, then our algorithm finds an independent set of size 2ᵗ in time NO(t). This gives an approximation ratio of N/2Ω(√log N) in time NO(√log N), improving on the approximation ratio N/2^Ω((log N)1/3) obtained by Lovett [Lov26]. A limitation of this form of analysis follows from the integrality gaps of Tulsiani [Tul09]. These gaps imply that a universal guarantee of the form LasR(t)(G)≥2⁻ᵗNα(G)≥2ᵗ, at 2o(√log Nloglog N) levels, cannot hold over a range extending beyond t=O(√log Nloglog N). Thus, the exponent $1/2$ is the limit of this form of analysis, up to a factor of √loglog N.