# $\tilde{\text{O}}$ptimal Distributed Maximum Flow Approximation in Undirected Planar Graphs

Preprint · Yaseen Abd-Elhaleem, Michal Dory, Oren Weimann

- Archive id: arxiv:2608.09500
- Published: 2026-08-10
- arXiv: https://arxiv.org/abs/2608.09500
- Source URL: https://arxiv.org/abs/2608.09500
- PDF: https://arxiv.org/pdf/2608.09500
- Provenance: arxiv

## Abstract

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$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.