Bilu-Linial stability, certified algorithms and the Independent Set problem
Bilu-Linial stability, certified algorithms and the Independent Set problem
复制标题
DOI：
10.4230/lipics.esa.2019.7
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Haris Angelidakis;Pranjal Awasthi;Avrim Blum;Vaggos Chatziafratis;Chen Dan
中科院分区：
文献类型：
--
作者：
Haris Angelidakis;Pranjal Awasthi;Avrim Blum;Vaggos Chatziafratis;Chen Dan
我们根据 Bilu 和 Linial (2010) 引入的稳定性概念研究最大独立集 (MIS) 问题：如果 MIS 的加权实例具有唯一的最优解，并且在权重乘性扰动最多为 $\gamma\geq 1$ 的情况下仍保持唯一最优，则 MIS 的加权实例是 $\gamma$ 稳定的。然后的目标是有效地恢复唯一的最优解决方案。在这项工作中，我们在几个图类上求解 MIS 的稳定实例：我们求解最大度 $\Delta$ 的图上的 $\widetilde{O}(\Delta/\sqrt{\log \Delta})$-稳定实例、$k$-可着色图上的 $(k - 1)$-稳定实例以及平面图上的 $(1 + \varepsilon)$-稳定实例。对于一般图，我们提出了一个强大的下界，表明假设植集团猜想，对于 MIS 的 $O(n^{\frac{1}{2} - \varepsilon})$ 稳定实例没有有效的算法。我们还给出了 $(\varepsilon n)$ 稳定实例的算法。作为我们技术的副产品，我们给出了 Node Multiway Cut 稳定实例的算法和下限。此外，我们证明了一个一般结果，表明几个最大化问题的凸松弛的完整性差距在稳定实例上显着减小。此外，我们启动了认证算法的研究，这是 Makarychev 和 Makarychev (2018) 最近提出的一个概念，它是一类满足一个关键属性的 $\gamma$ 近似算法：返回的解决方案对于原始实例的扰动是最优的。我们在最大度 $\Delta$ 的图上获得了 $\Delta$ 认证的 MIS 算法，在平面图上获得了 $(1+\varepsilon)$ 认证的算法。最后，我们分析了 Berman 和 Furer (1994) 的算法，并证明它是在最大度 $\Delta$ 图上所有权重都等于 1 的 MIS 的 $\left(\frac{\Delta + 1}{3} + \varepsilon\right)$ 认证算法。
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.