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

Haris Angelidakis, Pranjal Awasthi, Avrim Blum +2

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 o…