$\tilde{\text{O}}$ptimal Distributed Maximum Flow Approximation in Undirected Planar Graphs
2026-08-10 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms
AI summaryⓘ
The authors improve distributed algorithms for finding nearly the best way to push flow between two points in undirected planar graphs, working in fewer communication rounds. They remove previous limitations that required the start and end points to lie on the same face of the graph and eliminate extra slow factors in runtime. Their approach is based on adapting a classic centralized algorithm by Reif through careful operations on the graph's dual, despite only being able to communicate on the original graph. This results in a faster, more general algorithm for the maximum flow problem in planar graphs.
Distributed algorithmsPlanar graphsMaximum st-FlowApproximation algorithmReif's algorithmGraph dualityHop-diameterRecursive incisionCommunication roundsUndirected graphs
Authors
Yaseen Abd-Elhaleem, Michal Dory, Oren Weimann
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$.