Bilu-Linial stability, certified algorithms and the Independent Set problem

We study the Maximum Independent Set (MIS) problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of MIS is γ-stable if it has a unique optimal solution that remains the unique optimum under multiplicative perturbations of the weights by a factor of at most γ≥ 1. The goal then is to efficiently recover the unique optimal solution. In this work, we solve stable instances of MIS on several graphs classes: we solve widetildeO(Delta/√log Delta)-stable instances on graphs of maximum degree Delta, (k - 1)-stable instances on k-colorable graphs and (1 + varepsilon)-stable instances on planar graphs. For general graphs, we present a strong lower bound showing that there are no efficient algorithms for O(n^frac12 - varepsilon)-stable instances of MIS, assuming the planted clique conjecture. We also give an algorithm for (varepsilon n)-stable instances. As a by-product of our techniques, we give algorithms and lower bounds for stable instances of Node Multiway Cut. Furthermore, we prove a general result showing that the integrality gap of convex relaxations of several maximization problems reduces dramatically on stable instances. Moreover, we initiate the study of certified algorithms, a notion recently introduced by Makarychev and Makarychev (2018), which is a class of γ-approximation algorithms that satisfy one crucial property: the solution returned is optimal for a perturbation of the original instance. We obtain Delta-certified algorithms for MIS on graphs of maximum degree Delta, and (1+varepsilon)-certified algorithms on planar graphs. Finally, we analyze the algorithm of Berman and Furer (1994) and prove that it is a left(fracDelta + 13 + varepsilonright)-certified algorithm for MIS on graphs of maximum degree Delta where all weights are equal to 1.