MAX-CUT has a randomized approximation scheme in dense graphs

✍ Scribed by W. Fernandez de la Vega

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 508 KB
• Volume: 8
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199605)8:3<187::aid-rsa3>3.0.co;2-u

✦ Synopsis

A cut in a graph G = (V(G), E(G)) is the boundary 6(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 < a < 1, E > 0, and 17, 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 >an, outputs a cut S(S) of G with

We also show that the proposed method can be used to approximate MAXIMUM ACYCLIC SUBGRAPH in the unweighted case.