Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree
Given a graph G of degree k over n vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth L, we develop a local message passing algorithm whose complexity is O(nkL), and that achieves near optimal cut values among all L-local algorithms. Focusing on max-cut, the algorithm constructs a cut of value nk/4+ nπ―_ββ(k/4)+πΎππ(n,k,L), where π―_ββ 0.763166 is the value of the Parisi formula from spin glass theory, and πΎππ(n,k,L)=o_n(n)+no_k(β(k))+n β(k) o_L(1) (subscripts indicate the asymptotic variables). Our result generalizes to locally treelike graphs, i.e., graphs whose girth becomes L after removing a small fraction of vertices. Earlier work established that, for random k-regular graphs, the typical max-cut value is nk/4+ nπ―_ββ(k/4)+o_n(n)+no_k(β(k)). Therefore our algorithm is nearly optimal on such graphs. An immediate corollary of this result is that random regular graphs have nearly minimum max-cut, and nearly maximum min-bisection among all regular locally treelike graphs. This can be viewed as a combinatorial version of the near-Ramanujan property of random regular graphs.
READ FULL TEXT