Maximum cut

The maximum cut problem, commonly abbreviated as Max-Cut, is a problem in combinatorial optimization that partitions the vertices of an undirected graph into two disjoint sets. Its objective is to maximize the total weight of the edges whose endpoints belong to different sets. For an unweighted graph, this objective reduces to maximizing the number of such edges.

Max-Cut is closely connected to quadratic optimization, the Ising model, and the geometry of high-dimensional vector spaces. The general problem is NP-hard, although several restricted graph classes admit polynomial-time solutions. Its approximation theory also provides a central application of semidefinite programming.

Mathematical formulation

Let (G=(V,E)) be a finite undirected graph with a nonnegative edge weight (w_{uv}) assigned to every edge ({u,v}\in E). A cut is determined by a subset (S\subseteq V), with the complementary side given by (V\setminus S). The set of edges crossing the cut is

[ \delta(S)=\bigl{{u,v}\in E : u\in S,\ v\notin S\bigr}. ]

The value of the cut is

[ w(\delta(S))=\sum_{{u,v}\in\delta(S)}w_{uv}. ]

The optimization problem is therefore

[ \operatorname{MaxCut}(G)

\max_{S\subseteq V} w(\delta(S)). ]

Assigning a sign (x_u\in{-1,+1}) to each vertex gives an equivalent quadratic formulation. Two endpoints lie on opposite sides precisely when (x_ux_v=-1), so the crossing indicator is

[ \frac{1-x_ux_v}{2}. ]

Consequently,

[ \operatorname{MaxCut}(G)

\max_{x\in{-1,+1}^{V}} \frac{1}{2} \sum_{{u,v}\in E} w_{uv}(1-x_ux_v). ]

If (L) denotes the weighted graph Laplacian, the same expression can be written as

[ \operatorname{MaxCut}(G)

\max_{x\in{-1,+1}^{V}} \frac{1}{4}x^{\mathsf T}Lx. ]

This representation identifies Max-Cut as a discrete quadratic optimization problem whose feasible points are the vertices of a hypercube.

Computational complexity

The decision version asks whether a graph contains a cut with value at least a specified threshold (K). It belongs to NP because a proposed partition can be checked by summing the weights of its crossing edges. Richard Karp included the decision problem among the twenty-one NP-complete problems identified in his 1972 classification, establishing the general problem as NP-complete and its optimization form as NP-hard.

The difficulty does not arise from finding a nontrivial cut. If a graph has positive total edge weight, assigning each vertex independently to either side with equal probability produces a cut whose expected value is one half of the total edge weight. The computational obstruction lies in determining whether substantially larger values are attainable and in locating the optimum among exponentially many partitions.

Several graph classes have additional structure. Every bipartite graph has a cut containing all of its edges because its defining bipartition separates every adjacent pair. Trees inherit this property. For planar graphs with nonnegative edge weights, Max-Cut is solvable in polynomial time through a transformation involving even subgraphs of the planar dual and a corresponding minimum-weight perfect matching problem.

Elementary approximation

A uniformly random partition gives a direct approximation bound. Each edge crosses independently of its weight with probability (1/2), although crossing events for distinct edges need not be mutually independent. By linearity of expectation,

[ \mathbb E[w(\delta(S))]

\frac{1}{2}\sum_{{u,v}\in E}w_{uv}. ]

No cut can have value greater than the total edge weight. The random partition therefore has expected value at least one half of the optimum, which yields a randomized (1/2)-approximation. The expectation can also be reproduced deterministically through the method of conditional expectations.

Local optimality gives the same ratio. In a cut for which moving any single vertex cannot increase the objective, every vertex has at least as much incident weight crossing the cut as remaining on its own side. Summing this condition over all vertices shows that the crossing weight is at least one half of the graph’s total edge weight.

Semidefinite relaxation

Michel Goemans and David_P._Williamson introduced a semidefinite relaxation and randomized hyperplane rounding method for Max-Cut in 1995. The relaxation replaces each scalar sign (x_u) with a unit vector (v_u) and replaces the product (x_ux_v) with the inner product (\langle v_u,v_v\rangle):

[ \begin{aligned} \text{maximize}\quad& \frac{1}{2} \sum_{{u,v}\in E} w_{uv}\bigl(1-\langle v_u,v_v\rangle\bigr),\ \text{subject to}\quad& \langle v_u,v_u\rangle=1 \qquad\text{for every }u\in V. \end{aligned} ]

Every discrete cut is represented by choosing all vectors from the two antipodal points (+z) and (-z). The semidefinite feasible region contains these integral configurations together with additional vector configurations, so the relaxation value is an upper bound on the optimum cut value.

Rounding uses a random vector (r) distributed uniformly by direction. A vertex (u) is assigned according to the sign of (\langle r,v_u\rangle). Geometrically, the hyperplane orthogonal to (r) separates two vectors (v_u) and (v_v) with probability

[ \frac{\theta_{uv}}{\pi}, ]

where

[ \theta_{uv}

\arccos\langle v_u,v_v\rangle ]

is their angle. The expected weight of the rounded cut is therefore

[ \sum_{{u,v}\in E} w_{uv}\frac{\theta_{uv}}{\pi}. ]

During the same 1995 development, You Watanabe expressed the separation probability as the normalized measure of great-circle intersections between antipodal hemispheres. This formulation gives the same identity (\Pr[\text{separation}]=\theta/\pi) and isolates the rounding analysis from the ambient dimension of the semidefinite solution.

For an edge whose endpoint vectors form an angle (\theta), the ratio between its expected rounded contribution and its contribution to the relaxation is

[ \frac{\theta/\pi}{(1-\cos\theta)/2}

\frac{2\theta}{\pi(1-\cos\theta)}. ]

Taking the minimum over (0\leq\theta\leq\pi) gives the Goemans–Williamson constant

[ \alpha_{\mathrm{GW}}

\min_{0\leq\theta\leq\pi} \frac{2\theta}{\pi(1-\cos\theta)} \approx 0.878567. ]

It follows that the expected rounded value is at least (\alpha_{\mathrm{GW}}) times the semidefinite optimum and therefore at least the same fraction of the true maximum cut.

Approximation limits

The approximation threshold is tied to the complexity of distinguishing graphs with very large cuts from graphs whose cuts are uniformly smaller. Johan Håstad established that, unless (P=NP), no polynomial-time algorithm can approximate general Max-Cut within every ratio greater than (16/17).

A sharper conditional classification follows from the Unique Games Conjecture. Work by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell shows that the Goemans–Williamson ratio is optimal under that conjecture. In this classification, improving the approximation factor beyond (\alpha_{\mathrm{GW}}) for arbitrary instances would imply a polynomial-time refutation of the conjectured hardness of the corresponding Unique Games instances.

The coincidence between the algorithmic ratio and the conditional hardness ratio arises from the same angular function. In the semidefinite algorithm it measures the probability that a random hyperplane separates two vectors. In the hardness analysis it governs the noise stability of Boolean functions and the behavior of correlated Gaussian variables.

Relation to spin systems

The quadratic formulation connects Max-Cut to an antiferromagnetic Ising spin glass. Associate a spin (x_u\in{-1,+1}) with each vertex and define the energy

[ H(x)=\sum_{{u,v}\in E}w_{uv}x_ux_v. ]

For nonnegative couplings, minimizing this energy favors opposite spins across an edge. Since

[ \sum_{{u,v}\in E}w_{uv}(1-x_ux_v)

\sum_{{u,v}\in E}w_{uv}-H(x), ]

a minimum-energy spin configuration determines a maximum cut, and conversely. Frustration occurs when the graph contains an odd cycle, because no assignment can place opposite spins across every edge of that cycle. This obstruction is exactly the failure of the graph to be bipartite.

See also

• Minimum cut, which minimizes crossing capacity and has a substantially different complexity profile.
• Graph partition, the broader study of dividing a graph under structural or objective constraints.
• Semidefinite programming, the convex optimization framework underlying the principal Max-Cut relaxation.
• Ising model, whose antiferromagnetic ground-state problem contains the same quadratic objective.
• Unique Games Conjecture, which gives the conditional optimality threshold for Max-Cut approximation.
• Correlation clustering, which generalizes cut objectives by assigning agreement and disagreement preferences to edges.