×

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
PDF BibTeX XML Cite
Full Text: DOI