Approximating independent sets in sparse graphs
Bansal, N Nikhil · TU/e Research Portal · 2015
We consider the maximum independent set problem on sparse graphs with maximum degree d. The best known result for the problem is an SDP based O(d log log d/log d) approximation due to Halperin. It is also known that no o(d/ log2 d) approximation exists assuming the Unique Games Conjecture. We show the following two results: (i) The natural LP formulation for the problem strengthened by O(log4(d)) levels of the mixed-hierarchy has an integrality gap of Õ(d/log2 d), where Õ(·) ignores some log log d factors. However, our proof is non-constructive, in particular it uses an entropy based approach due to Shearer, and does not give a Õ(d/log2d) approximation algorithm with sub-exponential running time. (ii) We give an O(d/log d) approximation based on polylog(d)-levels of the mixed hierarchy that runs in nO(1) exp(logO(1) d) time, improving upon Halperin's bound by a modest log log d factor. Our algorithm is based on combining Halperin's approach together with an idea used by Ajtai, Erdös, Komlós and Szemerédi to show that Kr-free, degree-d graphs have independent sets of size Or(n log log d/d). Read More: http://epubs.siam.org/doi/abs/10.1137/1.9781611973730.1