Maximal cut

For a graph, a maximal cut is a cut with the size not smaller than the size of any other cut. The problem of finding a maximal cut is a graph is known as the max-cut problem.

Max-cut problem

The max-cut problem is one of Karp's 21 NP-complete problems; the proof comes by transformation from maximum 2-satisfiability (a restriction of the maximum satisfiability problem). Consequently no polynomial-time algorithms for max-cut can be expected.

A polynomial-time algorithm to find maximum cuts in planar graphs exists.

Various meta-heuristic search methods can sometimes efficiently produce approximate solutions. There is a simple 0.5-randomized approximation algorithm: for each vertex flip a coin to decide to which half of the partition to assign it. The best known max-cut algorithm is the $0.878$…-approximation algorithm by Goemans and Williamson using semidefinite programming and randomized rounding.

The max cut problem is APX-hard, meaning that there is no polynomial-time approximation scheme (PTAS) for it unless P = NP. Moreover, Hastad has shown that it is NP-hard to approximate the max cut value to better than $16/17=0.941$…. Assuming the Unique Games Conjecture (UGC), it is in fact NP-hard to approximate the max cut value by a factor of $alpha\_\{GW\}\; +\; epsilon$ for any $epsilon\; >\; 0$, where $alpha\_\{GW\}\; =\; 0.878$… is the approximation factor of Goemans-Williamson. (In other words, assuming the UGC and that $BPP\; eq\; NP$, the Goemans-Williamson algorithm yields essentially the best polynomial-time-computable possible approximation ratio for the problem.)

ee also

*minimal cut

References

*R. M. Karp, "Reducibility among combinatorial problems", in R. E. Miller and J. W. Thacher (eds.), "Complexity of Computer Computation", Plenum Press, New York, 85-103 (1972)
*M. X. Goemans, and D. P. Williamson, [http://portal.acm.org/citation.cfm?id=227684 "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming"] , Journal of the ACM, 42, 6 (Nov. 1995), 1115-1145
*S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, [http://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf "Optimal inapproximability results for MAX-CUT and other two-variable CSPs?"] , In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 146–154, 2004.
*cite book|author = Michael R. Garey and David S. Johnson | year = 1979 | title = | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5 A2.2: ND16, pg.210.