Distributed Algorithms for Potential Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911456123944960 |
|---|---|
| author | Balliu, Alkida Boudier, Thomas d'Amore, Francesco Kuhn, Fabian Olivetti, Dennis Schmid, Gustav Suomela, Jukka |
| author_facet | Balliu, Alkida Boudier, Thomas d'Amore, Francesco Kuhn, Fabian Olivetti, Dennis Schmid, Gustav Suomela, Jukka |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12038 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed Algorithms for Potential Problems Balliu, Alkida Boudier, Thomas d'Amore, Francesco Kuhn, Fabian Olivetti, Dennis Schmid, Gustav Suomela, Jukka Distributed, Parallel, and Cluster Computing 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. |
| title | Distributed Algorithms for Potential Problems |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2507.12038 |