Premium
MAX‐CUT has a randomized approximation scheme in dense graphs
Author(s) -
Fernandez de la Vega W.
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199605)8:3<187::aid-rsa3>3.0.co;2-u
Subject(s) - combinatorics , mathematics , graph , boundary (topology) , minimum cut , discrete mathematics , mathematical analysis
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 < α < 1, ϵ > 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.