Fully Dynamic All-Pairs Min Cuts on Planar Graphs via Planar Pattern Emulators
cs.DS
Submitted: 2026-10-28
Updated: 2026-10-28
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the fully-dynamic all-pairs minimum cut problem on planar graphs.
Abstract
We study the fully-dynamic all-pairs minimum cut problem on planar graphs. Given an n-vertex undirected planar graph G=(V,E) undergoing edge insertions and deletions, the goal is to efficiently process these updates while supporting s - t minimum cut queries for any pair of vertices s and t. We give a (1+ epsilon) -approximate dynamic algorithm that supports edge updates and minimum cut queries in n o(1) time, for any 1/poly(n) < epsilon < 1. For general graphs, previous results either are limited to partially dynamic settings or achieve only logarithmic-factor approximations. The main conceptual and technical contribution is to show that a suitable adaptation of the planar emulator of Chang, Krauthgamer, and Tan [STOC'22] satisfies the stronger pattern emulator introduced by Chen and Tan [ICALP'25]. This leads almost immediately to a nearly linear-time construction of pattern emulators, which, when combined with the recent fully dynamic (1+ epsilon) -approximate all-pairs shortest paths algorithm of Filtser, Goranci, Patel, and Probst Gutenberg [FOCS'24], yields our result.
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles