In this work we present a fast distributed algorithm for local potential problems: these are graph problems where the task is to find a locally optimal solution where no node can unilaterally improve the utility in its local neighborhood by changing its own label. A simple example of such a problem is the task of finding a locally optimal cut, i. e. , a cut where for each node at least half of its incident edges are cut edges. The distributed round complexity of locally optimal cut has been wide open; the problem is known to require Ω (n) rounds in the deterministic LOCAL model and Ω (n) rounds in the randomized LOCAL model, but the only known upper bound is the trivial brute-force solution of O (n) rounds. Locally optimal cut in bounded-degree graphs is perhaps the simplest example of a locally checkable labeling problem for which there is still such a large gap between current upper and lower bounds. We show that in bounded-degree graphs, all local potential problems, including locally optimal cut, can be solved in ^O (1) n rounds, both in the deterministic and randomized LOCAL models. In particular, the deterministic round complexity of the locally optimal cut problem is now settled to ^Θ (1) n.
Balliu et al. (Wed,) studied this question.