CS Paper Radar

Fully Dynamic All-Pairs Min Cuts on Planar Graphs via Planar Pattern Emulators

Arnold Filtser, Gramoz Goranci, Ali Momeni, Neel Patel, Maximilian Probst Gutenberg

cs.DS ·submitted 2026-10-28 19:24 UTC · v1

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+\varepsilon)$-approximate dynamic algorithm that supports edge updates and minimum cut queries in $n^{o(1)}$ time, for any $1/\text{poly}(\log n) < \varepsilon < 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+\varepsilon)$-approximate all-pairs shortest paths algorithm of Filtser, Goranci, Patel, and Probst Gutenberg~[FOCS'24], yields our result.

Closest papers

Nearest neighbours by meaning across the whole index.

A Nearly Optimal Min-Cut Algorithm for Dynamic Streams

cs.DS ·2026-10-25 ·Yang P. Liu, Hoai-An Nguyen, Vihan Shah, David P. Woodruff
similarity 0.68
Abstract

We give an $\tilde{O}(n/\varepsilon)$-space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic factors. Ding, Garces, Li, Lin, Nelson, Shah, and Woodruff (ITCS 2025) obtained the same $\tilde{O}(n/\varepsilon)$ space bound for insertion-only streams, while prior to our work the best known bound even for unweighted dynamic streams was $\tilde{O}(n/\varepsilon^2)$, due to Ahn, Guha, and McGregor (PODS 2012). Our main technical contribution is an $\tilde{O}(n/\varepsilon)$-space for-each cut sketch in dynamic streams, which may be of independent interest. The construction applies to weighted graphs under general $\pmΔ$ updates, a stronger model than the standard dynamic-stream setting in which weighted edges are inserted and deleted in their entirety. Despite this stronger guarantee, our algorithm is surprisingly simple and relies on very little machinery. We also obtain applications to minimum $\ell_p$-norm $k$-partitioning for every fixed $k$, weighted correlation-clustering evaluation for two clusters, and for-each cut sketching in balanced directed graphs.

0.46

Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLL

cs.DS ·2026-11-04 ·Mohsen Ghaffari, Sijin Peng
similarity 0.68
Abstract

We give a dynamic algorithm that maintains a near-optimal edge coloring in constant expected time per update. For every fixed $ε>0$, the algorithm maintains a $(1+ε)Δ$ edge coloring under edge insertions and deletions in $\mathrm{poly}(1/ε)$ worst-case expected update time against an oblivious adversary, provided $Δ\geΔ_ε=\widetildeΘ(1/ε^2)$. The previous constant-time algorithm of Bhattacharya, Costa, Panski, and Solomon (BCPS) required $Δ\ge(\log n/ε^4)^{Θ(\log(1/ε)/ε)}$, where $n$ is the number of vertices. We remove this dependence on $n$, answering their open question. Our approach differs substantially from that of BCPS, which relied on coloring in locally tree-like subgraphs. Instead, we draw on distributed algorithms that organize partial coloring through successive applications of the Lovász Local Lemma (LLL). We develop a dynamic LLL solver with worst-case expected update bounds and a dynamic splitting algorithm that partitions edges into low-degree subgraphs. A key technical contribution is a bottom-up method for iterative splitting, which avoids the logarithmic overhead of maintaining successive levels. It achieves constant expected update time by adaptively choosing which levels to inspect and repair, rather than inspecting every level after each update. We believe these dynamic splitting and LLL tools can be of interest beyond edge coloring.

0.20

Breaking Two Barriers for Dynamic Planar Reachability

cs.DS ·2026-10-09 ·Adam Karczmarz, Michał Włodarczyk
top venuetheory similarity 0.66
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

Deterministic Global Minimum Cut Using $\tilde{O}(n^{3/2})$ Cut Queries

cs.DS ·2026-10-16 ·Yotam Kenneth-Mordoch
published similarity 0.65
Abstract · Accepted at SOSA 2027

Finding a global minimum cut in an unweighted graph is a fundamental task in the cut-query model. While there exists a randomized algorithm for this task using $\tilde O(n)$ queries, known deterministic algorithms use $\tilde{O}(n^{5/3})$ queries. We improve upon this result and give a simple deterministic algorithm that finds a global minimum cut using $\tilde O(\min\left\{ nδ,n^2/δ\right\})$ cut queries, which equals $\tilde{O}(n^{3/2})$ in the worst case, where $δ$ is the minimum degree of the graph. The key ingredient in our approach is an efficient maximum $s,t$-flow algorithm, for the case when the minimum $s,t$-cut has value at most $δ$.

0.28

Quasi-polynomial-sized vertex multicut-mimicking networks and kernelization for Vertex Multiway Cut

cs.DS ·2026-11-05 ·Eduard Eiben, Roohani Sharma, Magnus Wahlström
survey similarity 0.65
Abstract

We give deterministic polynomial-time constructions of vertex multicut-mimicking networks of quasi-polynomial size. Given a graph G, a terminal set T, and a positive integer c, our algorithm constructs a graph with |T|^7 c^{O( log c ) } vertices that preserves every minimum vertex multiway cut value of at most c, for every partition of the terminals. Setting c=|T| gives an exact vertex multicut-mimicking network with |T|^{O( log |T| ) } vertices, resolving an open question of Wahlström [ACM Transactions on Algorithms 2022], who showed a bound of κ^{O( log^3 κ)} for the edge multicut-mimicking variant, where κ:= \sum_{t \in T} |N_G(t)| is the capacity of the terminal set, which was later improved to κ^{O( log^2 κ)} by Anand, Lee, Li and Saranurak [STOC 2024]. As applications of our vertex multicut-mimicking network, we obtain deterministic kernels of size k^{O( log k )} for Vertex Multiway Cut, p^{O(1)} k^{O(log k)} for Vertex Multicut with p requests and |Γ|^{O(1)} k^{O( log k)} for Group Feedback Vertex Set, where k is the deletion budget and Γis a finite group. Our first kernelization result, in particular, resolves an open question by Wahlström [ACM Transactions on Algorithms 2022], which was reiterated in a recent survey on kernelization by Jansen [Computer Science Reviews 2026]. Also, to the best of our knowledge, our kernel for Vertex Multicut is the first one whose size is completely polynomial in p and (quasi-polynomial) super-polynomial only in k. Finally, again using our vertex multicut-mimicking network for graphs, we obtain a hyperedge multicut-mimicking network for hypergraphs, which preserves hypergraph edge-multicuts of size up to c, of size |T|^{O(1)} c^{O(log c)}. Our result removes the dependence on the rank of the hypergraph from the exponent of the size bound, that existed in prior work.

0.29

Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs

cs.DS ·2026-10-19 ·Rares-Darius Buhai, Suprovat Ghoshal, Neng Huang, Pravesh Kothari, Euiwoong Lee +2 more
theory similarity 0.65
Abstract · 70 Pages

We give a polynomial-time algorithm that achieves an $α_{GW} + \tildeΩ(1/d)$-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most $d$ constraints. This improves on the $α_{GW}+\tildeΩ(1/d^2)$-approximation guarantee of [Hsieh-Kothari, ICALP'23]. We also show a matching Unique Games hardness under randomized polynomial-time reductions, thereby proving that the gain on $α_{GW}$ is optimal up to $\mathrm{polylog}(d)$ factors. Here, $α_{GW} \approx 0.878$ is the approximation ratio of the Goemans-Williamson algorithm. Our results resolve an open question due to Raghavendra and refute his conjectured optimal approximation ratio of $α_{GW} + \tildeΩ(1/\sqrt{d})$. Our local improvement scheme can be thought of as using an adaptive (based on the neighbors) shift applied to the Gaussian before using the GW sign rounding. This allows us to implement a ``soft but simultaneous'' flipping decision at each vertex as opposed to hard but sequential flipping decisions in prior works. Our hardness results are based on a new sparsification lemma for graphs produced by the reduction from Unique Games [Khot-Kindler-Mossel-O'Donnell, SICOMP'07] that preserves the optimal values up to a factor of $1 \pm ε$ while subsampling to an average degree of only $\tilde{O}(1/ε)$. This is the first example of a CSP in which the optimal advantage on degree-$d$ instances is asymptotically smaller than $O(1/\sqrt{d})$ [Trevisan, STOC'01]. A key idea in the proof of our sparsification theorem establishes new bounds on the number of ``nearly optimal'' cuts in the output of the KKMO reduction. This step, in turn, relies on a new, robust inverse Majority-Is-Stablest theorem.

0.15

Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting

cs.DS cs.CG ·2026-09-24 ·Kyungjin Cho, Eunjin Oh, Sebastian Wiederrecht
similarity 0.64
Abstract · To apear in ISAAC 2026

We study the \textsc{$k$-Disjoint Paths} problem on a graph embedded on a surface with bounded Euler genus. Given a graph $G$ with $n$ vertices and $k$ vertex pairs embedded on a surface of Euler genus $g$, we present a $2^{O(k^2+g^2)}n$-time algorithm that computes $k$ pairwise vertex-disjoint paths connecting the given vertex pairs if such paths exist. Our approach relies on the decomposition of $G$ into $O(k+g)$ planar subgraphs while bounding the complexity of the boundaries between these subgraphs. This approach enables the use of techniques for compressing linkages in planar graphs. Moreover, our techniques yield two kernels of size polynomial in $k$, $g$, and the treewidth of the graph, and of size $2^{O(k+g)}$. These results extend recent advances on \textsc{$k$-Disjoint Paths} on planar graphs [Cho et al. SODA 2023] and [Włodarczyk and Zehavi FOCS 2023] to surface-embedded graphs.

0.20

Finding and Certifying Weighted Minimum Cuts with Cut Queries

cs.DS ·2026-11-02 ·Troy Lee
similarity 0.64
Abstract · 57 pages. v2: corrects cross-reference names (some lemmas, remarks, definitions and corollaries were labelled "Theorem"); no change in conte…

We study the deterministic and nondeterministic cut query complexity of minimum cut in undirected graphs with arbitrary nonnegative edge weights. For the nondeterministic case, we show that every $n$-vertex graph has an $O(n\log^2(2n))$-query certificate of its exact global minimum-cut value, such that any other nonnegatively weighted graph on the same vertex set that agrees on these queries has the same minimum cut value. A key ingredient is a way to certify a maximum $s$--$t$ flow value with only $O(n)$ cut queries. For the deterministic case we give an algorithm that finds an exact global minimum cut using $O(n^{3/2}\log^3(2n)(\log\log(2n))^2)$ cut queries. Previously no $O(n^{2-\varepsilon})$ deterministic bound was known for arbitrary nonnegatively weighted graphs. The algorithm follows Karger's two-respecting tree approach. The key new ingredient is a deterministic construction of a weak skeleton of the input graph $G$: an explicit weighted graph $H$ in which every minimum cut of $G$ is a $5/4$-approximate minimum cut.

0.25