Maximum cut

As the Max-Cut Problem is NP-hard, no polynomial-time algorithms for Max-Cut in general graphs are known.

However, in planar graphs, the Maximum-Cut Problem is dual to the route inspection problem (the problem of finding a shortest tour that visits each edge of a graph at least once), in the sense that the edges that do not belong to a maximum cut-set of a graph G are the duals of the edges that are doubled in an optimal inspection tour of the dual graph of G. The optimal inspection tour forms a self-intersecting curve that separates the plane into two subsets, the subset of points for which the winding number of the curve is even and the subset for which the winding number is odd; these two subsets form a cut that includes all of the edges whose duals appear an odd number of times in the tour. The route inspection problem may be solved in polynomial time, and this duality allows the maximum cut problem to also be solved in polynomial time for planar graphs.[3] The Maximum-Bisection problem is known however to be NP-hard.[4]

The Max-Cut Problem is APX-hard,[5] meaning that there is no polynomial-time approximation scheme (PTAS), arbitrarily close to the optimal solution, for it, unless P = NP. Thus, every known polynomial-time approximation algorithm achieves an approximation ratio strictly less than one.

There is a simple randomized 0.5-approximation algorithm: for each vertex flip a coin to decide to which half of the partition to assign it.[6][7] In expectation, half of the edges are cut edges. This algorithm can be derandomized with the method of conditional probabilities; therefore there is a simple deterministic polynomial-time 0.5-approximation algorithm as well.[8][9] One such algorithm starts with an arbitrary partition of the vertices of the given graph ${\displaystyle G=(V,E)}$ and repeatedly moves one vertex at a time from one side of the partition to the other, improving the solution at each step, until no more improvements of this type can be made. The number of iterations is at most ${\displaystyle |E|}$ because the algorithm improves the cut by at least one edge at each step. When the algorithm terminates, at least half of the edges incident to every vertex belong to the cut, for otherwise moving the vertex would improve the cut. Therefore, the cut includes at least ${\displaystyle |E|/2}$ edges.

The polynomial-time approximation algorithm for Max-Cut with the best known approximation ratio is a method by Goemans and Williamson using semidefinite programming and randomized rounding that achieves an approximation ratio ${\displaystyle \alpha \approx 0.878,}$ where

${\displaystyle \alpha ={\frac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\frac {\theta }{1-\cos \theta }}.}$[10][11]

If the unique games conjecture is true, this is the best possible approximation ratio for maximum cut.[12] Without such unproven assumptions, it has been proven to be NP-hard to approximate the max-cut value with an approximation ratio better than ${\displaystyle {\tfrac {16}{17}}\approx 0.941}$.[13][14]

In [15] there is an extended analysis of 10 heuristics for this problem, including open-source implementation.

In statistical physics and disordered systems, the Max Cut problem is equivalent to minimizing the Hamiltonian of a spin glass model, most simply the Ising model.[16] For the Ising model on a graph G and only nearest-neighbor interactions, the Hamiltonian is

${\displaystyle H[s]=-\sum _{ij\in E(G)}J_{ij}s_{i}s_{j}}$

Here each vertex i of the graph is a spin site that can take a spin value ${\displaystyle s_{i}=\pm 1.}$ A spin configuration partitions ${\displaystyle V(G)}$ into two sets, those with spin up ${\displaystyle V^{+}}$ and those with spin down ${\displaystyle V^{-}.}$ We denote with ${\displaystyle \delta (V^{+})}$ the set of edges that connect the two sets. We can then rewrite the Hamiltonian as

${\displaystyle {\begin{aligned}H[s]&=-\sum _{ij\in E(V^{+})}J_{ij}-\sum _{ij\in E(V^{-})}J_{ij}+\sum _{ij\in \delta (V^{+})}J_{ij}\\&=-\sum _{ij\in E(G)}J_{ij}+2\sum _{ij\in \delta (V^{+})}J_{ij}\\&=C+2\sum _{ij\in \delta (V^{+})}J_{ij}\end{aligned}}}$

Minimizing this energy is equivalent to the min-cut problem or by setting the graph weights as ${\displaystyle w_{ij}=-J_{ij},}$ the max-cut problem.[16]

The max cut problem has applications in VLSI design.[16]