CS Paper Radar

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

Yaseen Abd-Elhaleem, Michal Dory, Oren Weimann

cs.DC cs.DS ·submitted 2026-08-10 12:04 UTC · v1
published

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

Comment
62 pages. 25 figures. A shortened version is to appear in DISC 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Shortest Paths and Maximum Flow in Planar Networks in the CONGEST Model

cs.DC ·2026-11-01 ·Sebastian Senge
theory similarity 0.76
Abstract

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

0.10

Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs

cs.DS ·2026-10-23 ·Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
similarity 0.68
Abstract · 101 pages

We give a combinatorial algorithm that computes an exact minimum-cost flow in $n^{2+o(1)}$ time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs. All previous faster algorithms, including the almost-linear-time algorithm of Chen et al. [CKL+22], rely on interior-point methods. Our main conceptual contribution is a black-box reduction from exact minimum-cost flow on general graphs to its approximation on DAGs, with only an $n^{o(1)}$ loss on the running time. This reduction allows future work on combinatorial minimum-cost flow to focus on DAGs, typically much easier to handle than general graphs. Our $n^{2+o(1)}$-time algorithm follows by combining this reduction with a simple augmenting-path-based approximation algorithm on DAGs. The reduction is based on a new structural result, called a flow-cost-preserving DAG projection. Given an arbitrary directed graph, this construction produces a DAG that approximately preserves both the congestion of flows and their cost up to a small loss.

0.48

On (Directed) Width-Parameters of Geometric Spanners

cs.CG ·2026-09-18 ·Kevin Buchin, Carolin Rehs, Torben Scheele
published similarity 0.68
Abstract · Accepted at ISAAC 2026

To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.

0.29

Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and More

cs.DS ·2026-10-12 ·Aditya Anand
theory similarity 0.66
Abstract · 46 pages, 5 figures. Corrected cross-reference labels caused by a TeX Live compatibility issue; mathematical content unchanged

We give a new rounding technique for spreading-metric linear programs, called Greedy Region Growing, which adapts the classical technique of region growing to min-max graph layout problems and flow-expander decomposition. Using this technique, we obtain state-of-the-art approximation algorithms for several fundamental problems. (1) An $O(\log n)$-approximation for Cutwidth and Pathwidth, improving upon the previous bound of $O(\log n\exp(O(\sqrt{\log\log n})))$ due to Bansal, Katzelnick, and Schwartz (FOCS 2024). This matches the $Ω(\log n)$ integrality gap of the standard LP relaxations. (2) An $O(\log n)$-approximation for their directed analogues, Minimum Storage and Minimum Register Sufficiency on directed acyclic graphs, improving the previous bound of $O(\log^{3/2} n)$. (3) A $φ$-flow-expander decomposition that cuts at most an $O(φ\log n\log\log n)$ fraction of the edges. This improves the $O(φ\log n\exp(O(\sqrt{\log\log n})))$ bound of Bansal, Jambulapati, and Saranurak (ICALP 2026), and is within an $O(\log\log n)$ factor of the graph-theoretic lower bound. The vertex version of our algorithm also gives an $O(\log n)$-approximation for Treedepth. In particular, our results answer several open problems of Bansal, Katzelnick, and Schwartz (FOCS 2024). Technically, we also solve the conceptual question raised by their work: our technique shows how to adapt Seymour recursion to min-max objectives, and constructs $O(1)$-weak local partitions in spreading metrics.

0.29

Approximation Algorithms for Asymmetric Multi-Path TSP

cs.DS ·2026-11-19 ·Manuel Christalla, Vera Traub
similarity 0.66
Abstract

Asymmetric Multi-Path TSP is the generalization of the Asymmetric Traveling Salesperson Problem where we are looking for $k$ walks, each with prescribed start $s_i$ and prescribed end $t_i$, such that every vertex is visited by at least one of the walks. The objective is to minimize the total length of all walks. In general, it is NP-hard to find any approximation for this problem in polynomial time (even if the approximation factor is allowed to depend on the number of vertices). We show that one can obtain an $O(k)$-approximation in time $n^{O(k)}$, answering an open question by Friggstad [2013]. For the special case where all tour start vertices $s_i$ are identical and all end vertices $t_i$ are identical, we obtain an $O(k)$-approximation in polynomial time, as well as an $(O(\frac{1}ε), 1+ε)$-bicriteria approximation. For the multi-depot setting, where $s_i =t_i$ for all $i$, we obtain a constant-factor approximation in polynomial time. Finally, our results imply improved constant-factor approximation algorithms for Asymmetric Regret-Bounded Vehicle Routing and unit-weight Path ATSP.

0.11

Breaking Two Barriers for Dynamic Planar Reachability

cs.DS ·2026-10-09 ·Adam Karczmarz, Michał Włodarczyk
top venuetheory similarity 0.65
Abstract · To appear at SODA 2027

We consider the reachability problem in fully dynamic directed planar graphs: the graph undergoes edge updates (insertions and deletions) and we receive queries asking if one vertex is reachable from another. The current-best online algorithm for dynamic planar reachability spends worst-case time $\widetilde{O}(n^{2/3})$ per query/update [Subramanian, ESA '93]. This can be improved to $\widetilde{O}(n^{1/2})$ in the offline setting or when the embedding is fixed [Diks and Sankowski, ESA '07]. Our contribution is twofold: 1. We present the first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting, obtaining time ${O}(n^{0.49})$ per query/update. This shows that the problem is easier than answering distance queries in a dynamic undirected planar graph, for which a conditional lower bound of $n^{1/2 - o(1)}$ is known [Abboud and Dahlgaard, FOCS '16]. Notably, this lower bound applies to both online and offline algorithms. 2. Second, in the general online setting we design a randomized data structure with amortized update and query time ${O}(n^{0.664})$. This is the first improvement upon the exponent $2/3$ in over three decades. The main engine behind our theorems is a new sparsification framework aimed at maintaining information about reachability. Specifically, we study digraphs through the lens of VC dimensionality of certain set systems. First, we design sparse reachability emulators for planar digraphs that preserve the VC dimension. Second, we utilize orderings with a low ``stabbing number'' [Chazelle and Welzl, Discrete Comput. Geom. '89] to compute subquadratic reachability emulators in subquadratic time whenever the VC dimension is bounded.

0.40

Nearly Optimal Sparse Navigable Graphs in General Metrics

cs.DS ·2026-10-29 ·Hongyi Chen, Tianyi Zhang
similarity 0.65
Abstract · 24 pages, 3 figures

We study approximation algorithms for constructing sparse navigable graphs in general metrics. Given an $n$-point metric $(P,d)$ and a parameter $α\ge1$, a directed graph on $P$ is $α$-navigable if, for every pair of distinct points $s,t\in P$, the source $s$ has an outgoing neighbor $p$ with $d(p,t)<d(s,t)/α$. The objective is to minimize the number of edges. Recent independent works of Khanna, Padaki, and Waingarten (2026) and Conway et al. (2026) give $O(\log n)$-approximation algorithms and show that an $o(\log n)$ approximation is NP-hard in general. Before our work, the best known running time for such an approximation for general $α\ge1$ was $\widetilde O(\min\{n\operatorname{OPT}_α,n^{2.5}\})$, where $\operatorname{OPT}_α$ is the minimum number of edges in an $α$-navigable graph. In this paper, we give a randomized algorithm that, with high probability, runs in $\widetilde O(n^2)$ time and achieves an $O(\log n)$ approximation for every $α\ge1$. In general, these guarantees are nearly optimal up to constant factors in the approximation and polylogarithmic factors in the running time.

0.20

Faster Planar Diameter using Pseudoline Envelopes

cs.DS cs.CG ·2026-11-03 ·Da Wei Zheng, Daniel Prigan
similarity 0.65
Abstract

We give an improved algorithm for weighted directed planar diameter that runs in $\widetilde{O}(n^{3/2})$ time. This improves upon the $\widetilde{O}(n^{5/3})$ time algorithm for weighted directed planar diameter of Gawrychowski, Kaplan, Mozes, Sharir, and Weimann [SIAM J. Comput. 2021] and the recent $\widetilde{O}(n^{8/5})$ time algorithm for unweighted undirected planar diameter of Fredslund-Hansen, Mozes, and Weimann [SOSA 2027]. The main new result is an improved data structure for computing the farthest vertex when given feasible planar distances to the vertices on the outer face. The critical insight is the fact that normalized distances to the vertices of a face behave like pseudolines, for which we can leverage range searching and upper envelope data structures. Using the farthest vertex data structure, we are able to compute all vertex eccentricities and diameter in $\widetilde{O}(n^{3/2})$.

0.24