Conjectures on phase transition at correlation clustering on random graphs

Abstract. The Correlation Clustering is a classical, NP hard optimization problem with many social, economic, physical, biological and computer science applications. We had implemented several methods to find near optimal solutions for particular problems. Here we summarize the results of our experiments on random graphs in particular with regard to phase transitions.