Abstract
We study the classic Maximum Independent Set problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of Independent Set is gammastable if it has a unique optimal solution that remains the unique optimal solution under multiplicative perturbations of the weights by a factor of at most gamma >= 1. The goal then is to efficiently recover this "pronounced" optimal solution exactly. In this work, we solve stable instances of Independent Set on several classes of graphs: we improve upon previous results by solving O~(Delta/sqrt(log Delta))stable instances on graphs of maximum degree Delta, (k  1)stable instances on kcolorable graphs and (1 + epsilon)stable instances on planar graphs (for any fixed epsilon > 0), using both combinatorial techniques as well as LPs and the SheraliAdams hierarchy.
For general graphs, we present a strong lower bound showing that there are no efficient algorithms for O(n^(1/2  epsilon))stable instances of Independent Set, assuming the planted clique conjecture. To complement our negative result, we give an algorithm for (epsilon n)stable instances, for any fixed epsilon > 0. As a byproduct of our techniques, we give algorithms as well as lower bounds for stable instances of Node Multiway Cut (a generalization of Edge Multiway Cut), by exploiting its connections to Vertex Cover. Furthermore, we prove a general structural 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 for Independent Set. The notion of a gammacertified algorithm was introduced very recently by Makarychev and Makarychev (2018) and it is a class of gammaapproximation algorithms that satisfy one crucial property: the solution returned is optimal for a perturbation of the original instance, where perturbations are again multiplicative up to a factor of gamma >= 1 (hence, such algorithms not only solve gammastable instances optimally, but also have guarantees even on unstable instances). Here, we obtain Deltacertified algorithms for Independent Set on graphs of maximum degree Delta, and (1+epsilon)certified algorithms on planar graphs. Finally, we analyze the algorithm of Berman and Fürer (1994) and prove that it is a ((Delta + 1)/3 + epsilon)certified algorithm for Independent Set on graphs of maximum degree Delta where all weights are equal to 1.
BibTeX  Entry
@InProceedings{angelidakis_et_al:LIPIcs:2019:11128,
author = {Haris Angelidakis and Pranjal Awasthi and Avrim Blum and Vaggos Chatziafratis and Chen Dan},
title = {{BiluLinial Stability, Certified Algorithms and the Independent Set Problem}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {7:17:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11128},
URN = {urn:nbn:de:0030drops111288},
doi = {10.4230/LIPIcs.ESA.2019.7},
annote = {Keywords: BiluLinial stability, perturbation resilience, beyond worstcase analysis, Independent Set, Vertex Cover, Multiway Cut}
}
Keywords: 

BiluLinial stability, perturbation resilience, beyond worstcase analysis, Independent Set, Vertex Cover, Multiway Cut 
Collection: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 