  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
$\gamma$-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 $\gamma\geq 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 $\widetilde{O}(\Delta/\sqrt{\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^{\frac{1}{2} - \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
$\gamma$-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(\frac{\Delta + 1}{3} + \varepsilon\right)$-certified algorithm for MIS
on graphs of maximum degree $\Delta$ where all weights are equal to 1.
