Maximum cut

For a graph, a maximum cut is a cut whose size is at least the size of any other 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. Finding such a cut is known as the max-cut problem. The problem can be stated simply as follows. One wants a subset S of the vertex set such that the number of edges between S and the complementary subset is as large as possible. Equivalently, one wants a bipartite subgraph of the graph with as many edges as possible. There is a more general version of the problem called weighted max-cut, where each edge is associated with a real number, its weight, and the objective is to maximize the total weight of the edges between S and its complement rather than the number of the edges. The weighted max-cut problem allowing both positive and negative weights can be trivially transformed into a weighted minimum cut problem by flipping the sign in all weights. Edwards obtained the following two lower bound for Max-Cut on a graph G with n vertices and m edges (in (a) G is arbitrary, but in (b) it is connected): (a) (b) Bound (b) is often called the Edwards-Erdős bound as Erdős conjectured it. Edwards proved the Edwards-Erdős bound using probabilistic method; Crowston et al. 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) on signed graphs G = (V, E, s), i.e. graphs where each edge is assigned + or –. For a partition of V into subsets U and W, an edge xy is balanced if either s(xy) = + and x and y are in the same subset, or s(xy) = – and x and y are different subsets. 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.