MAXk‐CUT and approximating the chromatic number of random graphs
Amin Coja‐Oghlan, Cristopher Moore, Vishal Sanwalani · Random Structures and Algorithms · 2005
Abstract We consider the MAXk‐CUT problem on random graphsGn,p. First, we bound the probable weight of a MAXk‐CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAXk‐CUT in expected polynomial time, with approximation ratio 1 +O((np)‐1/2). Our main technical tool is a new bound on the probable value of Frieze and Jerrum's semidefinite programming (SDP)‐relaxation of MAXk‐CUT on random graphs. To obtain this bound, we show that the value of the SDP is tightly concentrated. As a further application of our bound on the probable value of the SDP, we obtain an algorithm for approximating the chromatic number ofGn,p, 1/n≤p≤ 0.99, within a factor ofO((np)1/2) in polynomial expected time, thereby answering a question of Krivelevich and Vu. We give similar algorithms for random regular graphs. The techniques for studying the SDP apply to a variety of SDP relaxations of further NP‐hard problems on random structures and may therefore be of independent interest. For instance, to bound the SDP we estimate the eigenvalues of random graphs with given degree sequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006