2018/10/19 by Haris Angelidakis, Angelidakis, Haris, Pranjal Awasthi +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1810.08414
openalex publication_date 2018/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the Maximum Independent Set (MIS) problem under the notion of\nstability introduced by Bilu and Linial (2010): a weighted instance of MIS is\n\γ-stable if it has a unique optimal solution that remains the unique\noptimum under multiplicative perturbations of the weights by a factor of at\nmost \γ\≥ 1. The goal then is to efficiently recover the unique optimal\nsolution. In this work, we solve stable instances of MIS on several graphs\nclasses: we solve widetildeO(\Δ/\√(\log \Δ))-stable instances\non graphs of maximum degree \Δ, (k - 1)-stable instances on\nk-colorable graphs and (1 + \ε)-stable instances on planar graphs.\nFor general graphs, we present a strong lower bound showing that there are no\nefficient algorithms for O(n\(1)/(2) - \ε)-stable instances of\nMIS, assuming the planted clique conjecture. We also give an algorithm for\n(\ε n)-stable instances. As a by-product of our techniques, we give\nalgorithms and lower bounds for stable instances of Node Multiway Cut.\nFurthermore, we prove a general result showing that the integrality gap of\nconvex relaxations of several maximization problems reduces dramatically on\nstable instances.\n Moreover, we initiate the study of certified algorithms, a notion recently\nintroduced by Makarychev and Makarychev (2018), which is a class of\n\γ-approximation algorithms that satisfy one crucial property: the\nsolution returned is optimal for a perturbation of the original instance. We\nobtain \Δ-certified algorithms for MIS on graphs of maximum degree\n\Δ, and (1+\ε)-certified algorithms on planar graphs. Finally,\nwe analyze the algorithm of Berman and Furer (1994) and prove that it is a\n\(\(\Δ + 1)/(3) + \ε\)-certified algorithm for MIS\non graphs of maximum degree \Δ where all weights are equal to 1.\n