Approximation and intractability results for the maximum cut problem and its variants
David J. Haglin, Shankar M. Venkatesan · IEEE Transactions on Computers · 1991
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+ epsilon ) of its edges, where the positive constant epsilon 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>