{"ID":2893865,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.12038","arxiv_id":"2507.12038","title":"Distributed Algorithms for Potential Problems","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 $Ω(\\log n)$ rounds in the deterministic LOCAL model and $Ω(\\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^{Θ(1)} n$. Our algorithms also apply to the general case of graphs of maximum degree $Δ$. For the special case of locally optimal cut, we obtain a randomized algorithm that runs in $O(Δ^{2} \\log^{6} n)$ rounds, which can be derandomized at polylogarithmic cost with standard techniques. Furthermore, we show that a dependence in $Δ$ is necessary: we prove a lower bound of $Ω(\\min\\{Δ,\\sqrt{n}\\})$ rounds, even in the quantum-LOCAL model; in particular, there is no polylogarithmic-round algorithm for the general case.","short_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 find...","url_abs":"https://arxiv.org/abs/2507.12038","url_pdf":"https://arxiv.org/pdf/2507.12038v4","authors":"[\"Alkida Balliu\",\"Thomas Boudier\",\"Francesco d'Amore\",\"Fabian Kuhn\",\"Dennis Olivetti\",\"Gustav Schmid\",\"Jukka Suomela\"]","published":"2025-07-16T08:53:58Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false}