Metraipolis › archive › dc_38ea0bba21c8

Exact Shortest Paths and Maximum Flow in Planar Networks in the CONGEST Model — arXiv:2611.02256

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02256
License (as archived)
CC0-1.0
Archived
2026-11-03T18:26:42.144Z
SHA-256 of the archived text
441e07ba08c40bc0c2b7557252bdd1e57416863cf9c7fd12c0d92b7b28551c0f
Stable URL of this page
https://metraipolis.com/documento/dc_38ea0bba21c8

How to cite

Exact Shortest Paths and Maximum Flow in Planar Networks in the CONGEST Model — arXiv:2611.02256 — arXiv (en), https://arxiv.org/abs/2611.02256 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_38ea0bba21c8 (Metraipolis archive dc_38ea0bba21c8, sha256 441e07ba08c40bc0c2b7557252bdd1e57416863cf9c7fd12c0d92b7b28551c0f)
BibTeX
@misc{dc38ea0bba21c8,
  title = {Exact Shortest Paths and Maximum Flow in Planar Networks in the CONGEST Model — arXiv:2611.02256},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02256},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_38ea0bba21c8; sha256 441e07ba08c40bc0c2b7557252bdd1e57416863cf9c7fd12c0d92b7b28551c0f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02256. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In the CONGEST model, exact single-source shortest paths (SSSP) with nonnegative weights and exact maximum $st$-flow in directed planar networks have both been solved in $\tilde O(D^2)$ rounds, where $D$ is the hop diameter, while the lower bound is $\Omega(D)$. Given the approximate distance labels of a recent preprint ( arXiv:2606.31192 ), which we use as a black box, we solve exact directed SSSP in $\tilde O(D)$ rounds. It rests on a lemma that answers queries from a virtual source with the labels, and on a corrected discretization of the reduction of exact to approximate distances ( arXiv:2210.16351 ). All further bounds of the form $\tilde O(D)$ and $D\cdot n^{o(1)}$ use these labels. Through the reduction of arXiv:2303.00811 , SSSP with negative weights, or the detection of a negative cycle, takes $D\cdot n^{o(1)}$ rounds with high probability. We weight the face-disjoint graph of arXiv:2411.11718 so that its distances are dual distances, which turns distance problems in the dual into problems in a planar network of hop diameter $O(D)$. This gives exact maximum $st$-flow in directed planar networks in $\min\{\tilde O(D^2),D\cdot n^{o(1)}\}$ rounds with high probability, and in $\tilde O(D)$ rounds with $s,t$ on a common face. In undirected planar networks, the value of a minimum $st$-cut and a minimum cut take $\tilde O(D)$ rounds. For this we repair the auxiliary graphs of arXiv:2608.09500 at $s$ and $t$, and we show that its recursion, as we read it, can miss the minimum cut, also with exact shortest paths: on a network with $11$ vertices it reports $37$ for a minimum cut of $15$. Two more shortest-path computations per level make it exact. The virtual-source lemma, the weighting of the face-disjoint graph and the corrected discretization are machine-checked in Lean 4 with Mathlib; all other arguments are proved on paper only. Numerical checks are not used in any proof.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2611.02256 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:10:22.830Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).