MAX-CUT

'MAX-CUT'\' is the problem of partitioning the vertices of a graph into two sets so as to maximize the number of edges crossing between them. Formally, given an undirected graph G = (V, E) with edge weights w_ij, MAX-CUT seeks a subset S ⊆ V that maximizes the sum of w_ij over all edges (i, j) with i ∈ S and j ∉ S. It is one of the canonical NP-hard problems in combinatorial optimization, and its study has produced some of the deepest connections between theoretical computer science, statistical physics, and systems thinking.

Computational Complexity and the Limits of Exact Solution

MAX-CUT is NP-hard even for unweighted graphs, and it remains hard to approximate within any constant factor better than 0.878... unless the Unique Games Conjecture is false. This inapproximability threshold is not arbitrary: it reflects a precise boundary in the geometry of the semidefinite programming relaxation that underlies the best-known approximation algorithm.

The problem's hardness is not merely worst-case. In the average-case setting — where edges are drawn from specific distributions — MAX-CUT exhibits the same statistical-computational gap that characterizes planted clique and sparse PCA. Even when a planted partition exists and is information-theoretically detectable, no known polynomial-time algorithm reliably finds it in the conjectured hard regime. This places MAX-CUT at the center of debates about the nature of computational hardness: is the difficulty structural, or merely a failure of our algorithmic imagination?

The Goemans-Williamson Algorithm and Semidefinite Programming

The breakthrough of Goemans and Williamson (1995) showed that MAX-CUT can be approximated to within a factor of α_GW ≈ 0.878... using semidefinite programming. The algorithm embeds the graph into a high-dimensional sphere, solves an SDP relaxation, and rounds the solution using a random hyperplane. The analysis is remarkable: the rounding probability for each edge depends only on the angle between its endpoints in the SDP solution, and this angle is exactly what the 0.878 factor captures.

The Goemans-Williamson Algorithm is more than an approximation scheme. It revealed that the geometric structure of the semidefinite cone encodes information about combinatorial problems that linear programming cannot access. This insight launched the modern study of SDP-based approximation algorithms and connected combinatorial optimization to the geometry of convex bodies in ways that continue to yield surprises.

Connections to Physics: Ising Models and Spin Glasses

MAX-CUT has a deep and often underappreciated connection to statistical physics. The problem is equivalent to finding the ground state of an Ising model with antiferromagnetic couplings on the same graph. In this formulation, each vertex is a spin, each edge is a coupling, and the cut edges are precisely those where spins disagree. The energy landscape of this Ising model is rugged: exponentially many local minima correspond to locally optimal cuts, and the global optimum is hidden among them.

This physical interpretation makes MAX-CUT a natural meeting ground for ideas from spin glass theory. The replica symmetry breaking analysis of the Sherrington-Kirkpatrick model — in which pure states organize hierarchically — has direct analogues in the solution space structure of MAX-CUT on random graphs. The replica symmetry breaking transition in spin glasses corresponds precisely to the point at which local search algorithms fail to find the global optimum in MAX-CUT. The two fields are studying the same landscape from different elevations.

MAX-CUT in Systems and Networks

Beyond its theoretical importance, MAX-CUT appears in practical systems problems. In network science, it is closely related to community detection: partitioning a network to maximize between-group edges is the dual of finding tightly-knit communities. In signal processing, MAX-CUT formulations appear in synchronization problems and angular recovery. In machine learning, it underlies certain clustering objectives and relaxations of discrete optimization problems.

The problem also serves as a testbed for understanding average-case complexity. The Planted MAX-CUT model — in which a graph is generated with a hidden bipartition and noise is added — asks whether algorithms can recover the planted structure. Like planted clique, it exhibits regimes where detection is statistically possible but computationally hard, making it a canonical instance for studying the limits of efficient computation.

'The persistent fascination with MAX-CUT reveals something uncomfortable about how we judge progress in theoretical computer science. We celebrate the Goemans-Williamson algorithm as a triumph of convex relaxation, yet the 0.878 barrier has stood for three decades. The Unique Games Conjecture explains why, but a conjecture is not a theorem. I suspect the deeper reason is that MAX-CUT is not merely a combinatorial problem — it is a physical system, and physical systems do not yield to algorithmic ingenuity alone. The ground state of a spin glass is hard to find not because we lack clever algorithms, but because the landscape itself is computationally irreducible. Treating MAX-CUT as a discrete math problem and treating it as a physical system are not equivalent approaches; the physics view is the more honest one, and it tells us that some barriers may be permanent.'\