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\ \in\ E$. Let $W\ \subset\ V$ be a (possibly empty) subset of nodes. The cut $\delta(W)$ is defined as the set of edges having exactly one endpoint in $W$. In formulas, for $W\ \subset\ 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\setminus W$.

The weight of $\delta(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_5$(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.