The maximum cut

Min-cut is in P. Max-cut is NP-complete. The flip from min to max is enough to break tractability.

Max Cut partitions the vertex set into two sides and counts the edges that cross:

cut (S) = {u, v} \in E, ∣ S \cap {u, v} ∣ = 1 \sum w_{uv}, S \subseteq V . (1)

The problem is to maximize (1) over all partitions. Equivalently, assign each vertex a spin σ_v ∈ {−1, +1}; the Ising spin glass form is

max {u, v} \in E \sum w_{uv} \cdot \frac{1 - σ _{u} σ _{v}}{2} . (2)

Forms (1) and (2) are the same problem in graph-theoretic and physical clothing. NP-complete (Karp).

Goemans-Williamson 1995 — using semidefinite-program relaxation and random hyperplane rounding — achieves an approximation factor

α_{G W} \approx 0.87856. (3)

Unless the Unique Games Conjecture is false, the constant in (3) is optimal among polynomial-time algorithms (Khot et al.). Max Cut is the QAOA poster child: the Quantum Approximate Optimization Algorithm targets this exact problem on near-term quantum hardware.

Figures, in plain terms

(1)

cut(S) is a function: hand it a vertex subset S, get back a number — the total weight of edges that cross the cut.

The big-Σ sums over edges with a specific property. The condition under it — {u, v} ∈ E and |S ∩ {u, v}| = 1 — picks edges where exactly one endpoint sits in S (and the other in V\S).

The cardinality bars |S ∩ {u, v}| count how many of the two endpoints belong to S. Equal to 1 means the edge crosses the partition.

w_{uv} is the weight of edge {u, v}. For unweighted graphs, treat each weight as 1, and the cut value just counts crossing edges.

(2)

The Ising form names spins instead of subsets. σ_v ∈ {−1, +1} assigns each vertex a spin (think: up or down).

The big-Σ sums one term per edge. The term w_{uv} · (1 − σ_u σ_v)/2 uses a clever trick:

When σ_u = σ_v (same side), σ_u · σ_v = +1, so (1 − 1)/2 = 0 — the term contributes nothing.

When σ_u ≠ σ_v (opposite sides), σ_u · σ_v = −1, so (1 − (−1))/2 = 1 — the term contributes its full weight w_{uv}.

So the formula counts crossing edges by their weights, identical to (1) — just dressed in physics notation. Maximizing it is finding the spin assignment that maximizes "happy disagreement," which is also the ground state of an antiferromagnetic spin glass.

(3)

α_GW is the Goemans–Williamson approximation factor. The subscript credits the authors of the 1995 paper.

The value ≈ 0.87856 is a guarantee: their algorithm always returns a cut whose weight is at least 87.856% of the optimal cut's weight.

The constant comes from a specific integral over the unit hyperbolic — a real number with no closed form, but provably ≈ 0.87856. Under the Unique Games Conjecture, no polynomial-time algorithm beats this constant.