Maximum cut

That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible.

Edwards proved the Edwards-Erdős bound using probabilistic method; Crowston et al.[4] proved the bound using linear algebra and analysis of pseudo-boolean functions.

The proof of Crowston et al. allows us to extend the Edwards-Erdős bound to the Balanced Subgraph Problem (BSP) [4] on signed graphs G = (V, E, s), i.e. graphs where each edge is assigned + or –.

BSP aims at finding a partition with the maximum number b(G) of balanced edges in G. The Edwards-Erdős gives a lower bound on b(G) for every connected signed graph G. Bound (a) was improved for special classes of graphs: triangle-free graphs, graphs of given maximum degree, H-free graphs, etc., see e.g.[5][6][7] Poljak and Turzik[8] extended the Edwards-Erdős bound to weighted Max-Cut: where w(G) and w(Tmin) are the weights of G and its minimum weight spanning tree Tmin.

Recently, Gutin and Yeo[9] obtained a number of lower bounds for weighted Max-Cut extending the Poljak-Turzik bound for arbitrary weighted graphs and bounds for special classes of weighted graphs.

The canonical optimization variant of the above decision problem is usually known as the Maximum-Cut Problem or Max-Cut and is defined as: The optimization variant is known to be NP-Hard.

The opposite problem, that of finding a minimum cut is known to be efficiently solvable via the Ford–Fulkerson algorithm.

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.

[13] The Max-Cut Problem is APX-hard,[14] meaning that there is no polynomial-time approximation scheme (PTAS), arbitrarily close to the optimal solution, for it, unless P = NP.

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.

[17][18] One such algorithm starts with an arbitrary partition of the vertices of the given graph

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.

where If the unique games conjecture is true, this is the best possible approximation ratio for maximum cut.

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

While it is trivial to prove that the problem of finding a cut of size at least (the parameter) k is fixed-parameter tractable (FPT), it is much harder to show fixed-parameter tractability for the problem of deciding whether a graph G has a cut of size at least the Edwards-Erdős lower bound (see Lower bounds above) plus (the parameter)k. Crowston et al.[25] proved that the problem can be solved in time

Crowston et al.[25] extended the fixed-parameter tractability result to the Balanced Subgraph Problem (BSP, see Lower bounds above) and improved the kernel size to

Etscheid and Mnich [26] improved the fixed-parameter tractability result for BSP to

Treating its nodes as features and its edges as distances, the max cut algorithm divides a graph in two well-separated subsets.

In other words, it can be naturally applied to perform binary classification.

Compared to more common classification algorithms, it does not require a feature space, only the distances between elements within.

[27] 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.

We can then rewrite the Hamiltonian as Minimizing this energy is equivalent to the min-cut problem or by setting the graph weights as

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