# Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut

arXiv: https://arxiv.org/abs/1305.1681 · HTML: https://mlsanity.com/paper/1305.1681/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2013.

## Built on by (most cited first, 4 of 4)

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks](https://mlsanity.com/paper/2409.05100/) (2024)
- [Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances](https://mlsanity.com/paper/2103.00034/) (2021)
- [Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle](https://mlsanity.com/paper/2305.13402/) (2023)

## Abstract (arXiv)

We investigate the notion of stability proposed by Bilu and Linial. We obtain an exact polynomial-time algorithm for γ-stable Max Cut instances with γ ≥ c√log nloglog 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. Our algorithm is based on semidefinite programming. We show that the standard SDP relaxation for Max Cut (with ℓ22 triangle inequalities) is integral if γ ≥ Dℓ22→ ℓ1(n), where Dℓ22→ ℓ1(n) is the least distortion with which every n point metric space of negative type embeds into ℓ1. On the negative side, we show that the SDP relaxation is not integral when γ < Dℓ22→ ℓ1(n/2). Moreover, there is no tractable convex relaxation for γ-stable instances of Max Cut when γ < αSC(n/2). That suggests that solving γ-stable instances with γ =o(√log n) might be difficult or impossible. Our results significantly improve previously known results. The best previously known algorithm for γ-stable instances of Max Cut required that γ ≥ c√n (for some c > 0) [Bilu, Daniely, Linial, and Saks]. No hardness results were known for the problem. Additionally, we present an algorithm for 4-stable instances of Minimum Multiway Cut. We also study a relaxed notion of weak stability.