MAX-CUT has a randomized approximation scheme in dense graphs
W. Fernandez de la Véga · Random Structures and Algorithms · 1996
A cut in a graph G = (V(G), E(G)) is the boundary δ(S) of some subset S η V(G) and the maximum cut problem for G is to find the maximum number of edges in a cut. Let MC(G) denote this maximum. For any given 0 0, and η, we give a randomized algorithm which runs in a polynomial time and which, when applied to any given graph G on n vertices with minimum degree ≥αn, outputs a cut δ(S) of G with \documentclass{article}\pagestyle{empty}\begin{document}$ P[|\delta(S)|\geq MC(G)(1-\epsilon)] \geq 1-2^{-n} $\end{document} We also show that the proposed method can be used to approximate MAXIMUM ACYCLIC SUBGRAPH in the unweighted case. © 1996 John Wiley & Sons, Inc.