Max-cut

Problem formulation

In the max-cut problem we are given a graph G = (V,E) with edge weights $\scriptstyle c_{ij}\ \in\ \mathbb{R}$ for all edges e ∈ E. Let W ⊂ V be a (possibly empty) subset of nodes. The cut δ(W) is defined as the set of edges having exactly one endpoint in W. In formulas, for W ⊂ V the cut is defined as

$\delta(W) = \{(i,j)\ \in\ E|\ i\ \in\ W,\ j\ \in\ V\setminus W \}.\,\!$

In the following figure, the red edges are those in the cut. The set of nodes is partitioned into the black and orange nodes, one is the set W, the other its complement V\W.

The weight of δ(W) is sum of the weights of the edges in the cut, $\scriptstyle\sum\limits_{e\in\delta(W)} c_e$.

The max-cut problem is to find a cut of G with maximum weight. For a detailed study of the max-cut problem that covers many theoretical aspects, see [Deza and Laurent (1996)] . The max-cut problem can be generalized to the maximum-k-cut problem. In the latter, we need to assign the nodes of the graph to at most k sets so that the weighted sum of all edges having endpoints in distinct sets is maximized.

Complexity

The max-cut problem has been a topic of intensive research. It is a `classical' combinatorial optimization problem and one of the first that could be proven to be nondeterministic polynomial-time hard ($\scriptstyle\mathcal{NP}$-hard) on arbitrary graphs. Most people believe this means that the running time of any of its solution algorithms depends exponentially on the size of the input, in the worst-case.

Despite the $\scriptstyle\mathcal{NP}$-hardness of the general max-cut problem, there are some classes of graphs for which it is polynomially solvable, i.e., for which it can be solved in a number of elementary steps that is polynomially bounded by the number of bits needed to store the input data. The max-cut problem is polynomially solvable for graphs that are not contractable to K₅(the complete graph of five nodes) [Barahona (1983)]. This class of graphs include planar graphs, for more details see the article on planar max-cut. For non-positive edge weights, the problem can be solved in polynomial time via the famous maximum-flow minimum-cut duality. It is interesting to notice that max-cut is already $\scriptstyle\mathcal{NP}$-hard for almost planar graphs [Barahona (1983)] , i.e., graphs where only one node has to be removed to obtain a planar graph.

Exact solutions for max-cut

We determine optimum solutions for Max-Cut using branch-and-cut.

Approximating max-cut

Max-cut was the first problem for which approximation guarantees could be given with methods from positive semidefinite optimization. Goemans and Williamson [Goemans and Williamson (1994)] presented a 0.878-approximation for the maximum cut problem, i.e., an algorithm with running time bounded by a polynomial in the input size that provably delivers a solution of at least 0.878 times the optimum value of a maximum cut. However, the bad news is that under the assumption $\scriptstyle\mathcal{P}\ \ne\ \mathcal{NP}$ there is no polynomial algorithm that provably delivers a solution of at least 98% of the optimum value of a maximum cut.

Applications

One reason for the interest in the max-cut problem comes from the fact that it is equivalent to quadratic 0/1 programming. Finally, exact ground states of Ising spin glasses can be computed by calculating maximum cuts.