The NP-complete problems of partitioning and colouring of random graphs, with p partitions and colours respectively, are mapped onto the statistical mechanical problem of p-state Potts glasses. An estimate of the cost functions of these optimisation problems has been derived using the Potts glass mean-field theory. This estimate applies to dense graphs in the thermodynamic limit. An exact expression for the cost function in the large-p limit is given.
Graph Optimization Problems and the Potts Glass
Authors: I Kanter and H Sompolinsky
Year of publication: 1987
Journal: Journal of Physics A General Physics 20(11):L673
Link to publication: