• Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 16 Jul 2025 (v1), last revised 19 Feb 2026 (this version, v4)] Title:Distributed Algorithms for Potential Problems View PDF HTML (experimental)Abstract: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 the locally optimal cut problem has been wide open; the problem is known to require $\Omega(\log n)$ rounds in the deterministic LOCAL model and $\Omega(\log \log 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 constant-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 constant-degree graphs, all local potential problems, including locally optimal cut, can be solved in $\log^{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 $\log^{\Theta(

Article Summaries:

  • Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 16 Jul 2025 (v1), last revised 19 Feb 2026 (this version, v4)] Title:Distributed Algorithms for Potential Problems View PDF HTML (experimental)Abstract: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 e

Sources: