Title: The independent set problem on degree-d graphs
| Speaker: | Anupam Gupta |
| Affiliation: | Carnegie Mellon University |
| Room: | MC 6486 |
Abstract: The independent set problem on graphs with maximum degree d is known to be Omega(d/log^2 d) hard to approximate, assuming the unique games conjecture. However, the best approximation algorithm was worse by about an Omega(log d) factor. In a recent breakthrough, Bansal showed how to use few rounds of the SA+ hierarchy to estimate the size of the optimal independent set to within O~(d/log^2 d), essentially closing the gap. Some questions remained: could we find such an IS? And did we really need the SA+ lifting step?
In this talk, we show two results. Firstly, the standard SDP, based on the Lovasz Theta function, gives a O~(d/log^{3/2} d) approximation without using any lift/project steps. Secondly, using SA+, one can convert Bansal's algorithm for IS size estimation into an approximation algorithm. Both results, just like Bansal's, are based on Ramsay-theoretic results of independent interest.
This is based on joint work with Nikhil Bansal (TU Eindhoven) and Guru Guruganesh (CMU).