A Simple Message Passing Algorithm for Graph Partitioning
Mikael Onsjö, Osamu Watanabe · Chalmers Publication Library (Chalmers University of Technology) · 2006
Motivated by the belief propagation, we propose a simple and deterministic message passing algorithm for the Graph Bisection problem and related problems. The running time of the main algorithm is linear w.r.t. the number of vertices and edges. For evaluating its average-case correctness, planted solution models are used. For the Graph Bisection problem under the standard planted solution model with probability pa- rameters p and r, we prove that our algorithm yields a planted solution with probability > 1 − δ if p − r = Ω(n−1/2 log(n/δ)).