We investigate the notion of stability proposed by Bilu and Linial. We obtain an exact polynomialtime algorithm for γ-stable Max Cut instances with γ≥c(log n)~(1/2) log log n for some absolute constant c > 0. Our algorithm is robust: it never returns an incorrect answer; if the instance is -stable, it finds the maximum cut, otherwise, it either finds the maximum cut or certifies that the instance is not -stable. We prove that there is no robust polynomial-time algorithm forγ-stable instances of Max Cut when γ<α_(SC)(n/2), where α_(SC) is the best approximation factor for Sparsest Cut with non-uniform demands. That suggests that solving-stable instances with γ= o((log n)~(1/2)) might be difficult or even impossible. Additionally, we present an exact robust polynomial-time algorithm for 4-stable instances of Minimum Multiway Cut. We also study a relaxed notion of weak stability and present algorithms for weakly stable instances of Max Cut and Minimum Multiway Cut.
展开▼
