Approximation and intractability results for the maximum cut problem and its variants

The maximum cut problem is known to be an important NP-complete problem with many applications. The authors investigate this problem (which they call the normal maximum cut problem) and a variant of it (which is referred to as the connected maximum cut problem). They show that any n-vertex e-edge graph admits a cut with at least the fraction 1/2+1/2n of its edges, thus improving the ratio 1/2+2/e known before. It is shown that it is NP-complete to decide if a given graph has a normal maximum cut with at least a fraction (1/2+ε) of its edges, where the positive constant ε can be taken smaller than any value chosen. The authors present an approximation algorithm for the normal maximum cut problem on any graph that runs in O((e log e+n log n )/p+log p×log n) parallel time using p(1⩽p⩽e+n) processors that guarantees a ratio of at least [1/2+1/2n], given a matching of size e/n in G. The authors take up the connected maximum cut problem and show that, unlike the normal maximum cut problem, this problem admits an infinity of instances where the fraction of the edges in the connected maximum cut is arbitrarily close to zero. They then show that the connected maximum cut problem is NP-complete even for planar graphs, in clear contrast to the normal maximum cut problem, which is solvable in polynomial time on planar graphs