Max Cut for Random Graphs with a Planted Partition
B Bollobás, A. D. SCOTT · Combinatorics Probability Computing · 2004
We give an algorithm that, with high probability, recovers a planted $k$ -partition in a random graph, where edges within vertex classes occur with probability $p$ and edges between vertex classes occur with probability $r\ge p+c\sqrt{p\log n/n}$ . The algorithm can handle vertex classes of different sizes and, for fixed $k$ , runs in linear time. We also give variants of the algorithm for partitioning matrices and hypergraphs.