Max-cut
Contents
Problem formulation
In the max-cut problem we are given a graph with
edge weights
for all edges
. Let
be a (possibly empty) subset of nodes. The cut
is defined as the set of
edges having exactly one endpoint in
. In formulas, for
the cut is defined as
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 , the other its complement
.
The weight of is sum of the weights of the edges in the cut,
.
The max-cut problem is to find a cut of 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
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 (-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 -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
(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
-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 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.