MAX-CUT has a randomized approximation scheme in dense graphs. (English) Zbl 0848.90120

Summary: A cut in a graph \(G= (V(G), E(G))\) is the boundary \(\delta(S)\) of some subset \(S\subseteq V(G)\) and the maximum cut problem for \(G\) is to find the maximum number of edges in a cut. Let \(\text{MC}(G)\) denote this maximum. For any given \(0< \alpha< 1\), \(\varepsilon> 0\), and \(\eta\), 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 \(\geq \alpha n\), outputs a cut \(\delta(S)\) of \(G\) with \[ P[|\delta(S)|\geq \text{MC}(G)(1- \varepsilon)]\geq 1- 2^{- \eta}. \] We also show that the proposed method can be used to approximate MAXIMUM ACYCLIC SUBGRAPH in the unweighted case.


90C35 Programming involving graphs or networks
68R10 Graph theory (including graph drawing) in computer science
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI