Max-Cut Problem

The max-cut problem determines a subset of the vertices of a graph, for which the sum of the weights of the edges that cross from to its complement is maximized.

This example demonstrates how SemidefiniteOptimization may be used to set up a function that efficiently solves a relaxation of the NP-complete max-cut problem.

Suppose that has vertices so that they can be described by an index . Let be a vector with components for and for so that is nonzero (=2) only if and . Thus the max-cut is found by maximizing , where . The objective can be rewritten as:

... where is the Laplacian matrix of the graph and is the weighted adjacency matrix.

For smaller cases, the max-cut problem can be solved exactly, but this is impractical for larger graphs since in general the problem has NP-complete complexity.

The problem minimizes , where is a symmetric rank-1 positive semidefinite matrix, with for each , equivalent to , where is the matrix with at the diagonal position and 0 everywhere else.

To make the solution practical, solve a relaxed problem where the rank-1 condition is eliminated so that it only requires .

The semidefinite problem in dual form is given by

It is solved using SemidefiniteOptimization[c, {a0, a1, , ak}, {"DualMaximizer" }].

For the solution of the relaxed problem, a cut is constructed by randomized rounding: decompose , let be a uniformly distributed random vector of the unit norm and let . For demonstration, a function is defined that shows the relaxed value, the rounded value and the graph, with the vertices in shown in red.

Find an approximate max cut using the previously shown procedure, and compare with the exact result.

Find the max cut for a grid graph.

Find the max cut for a random graph.

Compare timings for the relaxed and exact algorithms for a Peterson graph.

Related Examples

ja