The MAX-CUT of sparse random graphs
Hervé Daudé, Conrado Martı́nez, Vonjy Rasendrahasina, Vlady Ravelomanana · 2012
A k-cut of a graph G = (V, E) is a partition of its vertex set into k parts; the size of the k-cut is the number of edges with endpoints in distinct parts. MAX-k-CUT is the optimization problem of finding a k-cut of maximal size and the case where k = 2 (often called MAX-CUT) has attracted a lot of attention from the research community. MAX-CUT—more generally, MAX-k-CUT— is NP-hard and it appears in many applications under various disguises. In this paper, we consider the MAX-CUT problem on random connected graphs ℂ(n, m) and on Erdős-Rényi random graphs G(n, m). More specifically, we consider the distance from bipartiteness of a graph G = (V, E), the minimum number of edge deletions needed to turn it into a bipartite graph. If we denote this distance DistBip(G), the size of the MAX-CUT of a graph G = (V, E) is clearly given by |E| − DistBip(G). Fix ε > 0. For random connected graphs, we prove that asymptotically almost surely (a.a.s) (DistBip whenever m = n + O(n1−ε). For sparse random graphs we show that DistBip ( (n, m)) is a.a.s about .