Premium
MAX k ‐CUT and approximating the chromatic number of random graphs
Author(s) -
CojaOghlan Amin,
Moore Cristopher,
Sanwalani Vishal
Publication year - 2006
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/rsa.20096
Subject(s) - combinatorics , mathematics , random graph , upper and lower bounds , eigenvalues and eigenvectors , discrete mathematics , semidefinite programming , maximum cut , time complexity , relaxation (psychology) , expected value , degree (music) , graph , mathematical optimization , statistics , mathematical analysis , physics , quantum mechanics , psychology , social psychology , acoustics
We consider the MAX k ‐CUT problem on random graphs G n , p . First, we bound the probable weight of a MAX k ‐CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAX k ‐CUT in expected polynomial time, with approximation ratio 1 + O (( n p ) ‐1/2 ). Our main technical tool is a new bound on the probable value of Frieze and Jerrum's semidefinite programming (SDP)‐relaxation of MAX k ‐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 of G n , p , 1/ n ≤ p ≤ 0.99, within a factor of O (( n p ) 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