Simple Algorithms for Graph Partition Problems
Mikael Onsjö, Osamu Watanabe · 2005
Based on the Belief Propagation Method, we propose simple and deterministic algorithms for some NP-hard graph partitioning problems, such as the Most Likely Partition problem and the Graph Bisection problem. These algorithms run in O(n+m) or O((n+m) log n) time on graphs with n vertices and m edges. For their average case analysis, we consider the planted solution model and prove that they yield an correct answer with high probability for large range of probabilistic parameters.