## 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.

### MSC:

 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: