Metraipolis › archive › dc_d13ea706e910

$\tilde{\text{O}}$ptimal Distributed Maximum Flow Approximation in Undirected Planar Graphs — arXiv:2608.09500

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.09500
License (as archived): CC0-1.0
Archived: 2026-10-19T08:52:41.709Z
SHA-256 of the archived text: 2c85adbfd708b5f7e984bfe5888ebcfc419f274eed75c750522586899a73ae3c
Stable URL of this page: https://metraipolis.com/documento/dc_d13ea706e910

How to cite

$\tilde{\text{O}}$ptimal Distributed Maximum Flow Approximation in Undirected Planar Graphs — arXiv:2608.09500 — arXiv (en), https://arxiv.org/abs/2608.09500 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d13ea706e910 (Metraipolis archive dc_d13ea706e910, sha256 2c85adbfd708b5f7e984bfe5888ebcfc419f274eed75c750522586899a73ae3c)

BibTeX

@misc{dcd13ea706e910,
  title = {$tildetextO$ptimal Distributed Maximum Flow Approximation in Undirected Planar Graphs — arXiv:2608.09500},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.09500},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d13ea706e910; sha256 2c85adbfd708b5f7e984bfe5888ebcfc419f274eed75c750522586899a73ae3c},
  year = {2026}
}

Archived text

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

Persistent efforts in recent years have been devoted to devising distributed algorithms for fundamental optimization problems in planar graphs. In particular, for Single-Source Shortest-Paths, there is an $\tilde O(D^2)$-rounds exact algorithm [Li, Parter STOC'19] for directed planar graphs, and an $\tilde {O}(D)$-rounds $(1+o(1))$-approximation algorithm [Rozhon, Grunau, Haeupler, Zuzic, Li STOC'22] for undirected planar graphs (where $D$ is the graph's hop-diameter). Recently [Abd-Elhaleem, Dory, Parter, Weimann PODC'25], a matching bound for the exact case was obtained for the Maximum $st$-Flow problem. Namely, an $\tilde O(D^2)$-rounds exact algorithm for directed planar graphs. However, for the approximate case, they give a $D\cdot n^{o(1)}$-rounds $(1-o(1))$-approximation algorithm for undirected planar graphs that works only for the special case where both $s$ and $t$ lie on the same face. In this paper, we remove the restriction that both $s$ and $t$ must lie on the same face (we also eliminate the $n^{o(1)}$ factor). Namely, we present the first distributed near-optimal $\tilde{O}(D)$-rounds $(1-o(1))$-approximation algorithm for Maximum $st$-Flow in general undirected planar graphs. Our main technical contribution is a distributed implementation of the classical Reif's [SICOMP'83] centralized algorithm. This is achieved by a careful recursive incision procedure on the planar dual $G^*$ of the graph $G$. It is challenging, because we need to simulate dynamic changes (incisions) over the dual graph $G^*$, while we can only communicate over the input graph $G$.

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-08-11 in cs.DC).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.09500 — 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-10-19T08:50:23.756Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).