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. In this paper, we investigate this problem (which we call the normal maximum cut problem) and a variant of it (which we call the connected maximum cut problem). Our main result are as follows. 1) We 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 befor. 2) We show 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 of our choice. 3) We exhibit, however, 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 less-than-or-equal-to p less-than-or-equal-to e + n) processors, that guarantees a ratio of at least [1/2 + 1/2n], given a matching of size e/n in G. 4) We 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. 5) We 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.