CS Paper Radar

An Optimal Structure for All-Pairs Nearest Mincuts and Sensitivity Oracles for Edge Insertions

Koustav Bhanja, Yotam Kenneth-Mordoch, Asaf Petruschka

cs.DS ·submitted 2026-09-25 14:00 UTC · v1

Abstract

Given an undirected weighted graph $G=(V,E)$ on $n$ vertices, the classical Gomory-Hu tree of $G$ is a structure that encodes an arbitrary minimum $s,t$-cut for every $s,t\in V$ using just $O(n)$ space. In this work, we ask whether the same compactness is achievable for the natural and structured family of all-pairs \textit{nearest minimum cuts}. The nearest minimum $(s,t)$-cut is the unique inclusion-wise minimal one among all minimum $s,t$-cuts containing $s$. This family has proven useful in a wide range of applications, including fault-tolerant reachability, minimum cut sensitivity oracles, cactus representations, and fast Gomory-Hu tree constructions. Despite its fundamental role, no subquadratic space representation is known for them to date. The $O(n)$ space representations are known only in single-source settings, where given a source $s$, one can report the nearest minimum $(t,s)$-cut for any $t\in V\setminus \{s\}$. We close this gap by presenting the first optimal space representation of all-pairs nearest minimum cuts, providing a natural analogue of the Gomory-Hu tree. Our main result is an $O(n)$ space structure that encodes the nearest minimum cut between every pair of vertices. Furthermore, given any pair $s,t\in V$, it can report the nearest minimum $s,t$-cut in $O(n)$ time. Both bounds match those of the Gomory-Hu tree and are worst-case optimal. As an application, we design an all-pairs minimum cut sensitivity oracle for edge insertion: a data structure that occupies $O(n)$ space and, given any edge $e$, can determine for all pairs $s,t\in V$ whether the minimum $s,t$-cut value increases upon insertion of $e$ in $O(n^2)$ total time. Existing insertion sensitivity oracles were either limited to the single-source setting or used $O(n^2)$ space for all-pairs [Baswana, Gupta, and Knollmann, Algorithmica'22; Baswana and Pandey, SODA'22].

Closest papers

Nearest neighbours by meaning across the whole index.

Beyond Gomory-Hu: All-Pairs $\times$ All-Pairs Mincuts in $O(n)$ Space

cs.DS ·2026-11-04 ·Koustav Bhanja, Merav Parter, Asaf Petruschka
similarity 0.75
Abstract

For over four decades, two classical structures have offered complementary views of mincuts. The Gomory-Hu tree encodes one $(x,y)$-mincut for every vertex pair $x,y$ in $O(n)$ space, but retains only one mincut per pair. In contrast, for a fixed pair $x,y$, the Picard-Queyranne representation admits an $O(n)$ space vertex ordering that determines whether some $(x,y)$-mincut separates any given pair $u,v$ and reports such a cut. Can these complementary guarantees hold simultaneously in $O(n)$ space? We answer affirmatively. For undirected graphs, we construct an $O(n)$ space structure encoding, for every four vertices $x,y,u,v$, an $(x,y)$-mincut separating $u,v$ whenever one exists. More precisely, given any terminal pair $x,y$, the structure recovers the Picard-Queyranne ordering in $O(n)$ time. Thereafter, separability queries take $O(1)$ time, and reporting a separating mincut $C$ takes $O(|C|)$ time. Thus, information for all $Θ(n^4)$ choices of $x,y,u,v$ is encoded in $O(n)$ space. This is essentially the strongest information of this form that fits in $O(n)$ space: if one additionally requires the mincut to place $u$ on side of $x$ and $v$ on side of $y$, then $Ω(n^2)$ space is necessary even for fixed $x,y$. As a consequence, we obtain an $O(n)$ space all-pairs mincut sensitivity oracle for a single edge failure in multigraphs, with optimal $O(n)$ time to report a new mincut. This resolves an open question of Baswana and Pandey [SODA'22] on achieving $o(n^2)$ space and $o(m)$ query time simultaneously. Our construction substantially generalizes the $O(n)$ space nearest-mincut-hierarchy [SODA'27], which reports only the nearest $(x,y)$-mincut. Recovering the entire Picard-Queyranne ordering for an arbitrary pair requires new structural properties of the Dinitz-Vainshtein [STOC'94] connectivity carcass, extending its use beyond the Steiner mincuts it represents.

0.13

Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications

cs.DS ·2026-09-01 ·Keerti Choudhary, Amit Kumar, Lakshay Saggi
theory similarity 0.67
Abstract · 65 pages, 3 figures

Sensitivity oracles preprocess a graph so that queries can be answered after any $f$ edge insertions and deletions, without recomputing from scratch. For structural optimization problems the known landscape is limited: for flows and cuts, all known compact oracles handle only $f\le2$ failures; existing oracles for $s$- and global min-cut apply only to undirected graphs; and for matchings, arborescence and spanning-tree packings, and arboricity, no efficient oracle is known for $f>1$. We present a unified algebraic framework based on sensitivity oracles for matroid packing, covering, and parity of sparse linear matroids, yielding the first oracles supporting an arbitrary number $f$ of updates across all of these problems (all constructions randomized Monte-Carlo). Concretely, we obtain efficient oracles for exact $(s,t)$-max-flow/min-cut, resolving an open problem of Baswana, Bhanja, and Pandey (ICALP'22) with near-optimal space; for all-pairs $k$-bounded flow, generalizing the near-optimal reachability oracle of Brand and Saranurak (FOCS'19, the case $k=1$); the first oracles for any $f$ for directed $s$- and global min-cut; oracles for $k$-disjoint arborescences, $k$-disjoint spanning trees, colorful spanning trees, and arboricity; and oracles for the existence of an $α$-factor, with perfect matching as the case $α=1$. We further introduce the \emph{subset sensitivity model}, in which updates are confined to a susceptible edge set of size $σ$ fixed during preprocessing. Here we decouple updates from the matroid representation and eliminate the dependence on $k$ and the matroid density altogether: all of the above are supported with $\widetilde O(f^ω)$ query time and $O(fσ^2)$ space. We also prove a matching $Ω(\min\{σ^2,n^2\})$-bit lower bound when $f\ge2$, establishing optimality.

0.49

When is greedy exact for weighted minimum 3-cut?

cs.DS ·2026-10-26 ·Armando Rodado Amaris
theorycode/data similarity 0.63
Abstract · 16 pages. Lean 4 proofs and Python reproduction scripts are provided as ancillary files and at https://github.com/armandorodado/minimum-3cut…

The greedy algorithm for minimum 3-cut splits a global minimum-weight cut and then the cheaper of its two sides; it is a tight $4/3$-approximation. We show that it is exact, from every global minimum-weight cut, whenever some optimal 3-partition has two parts joined by total weight at least the weighted edge connectivity $λ$. This extends both theorems of Hochbaum and Shmoys from unweighted planar graphs to all weighted graphs, recovers the $4/3$ bound, and generalizes to minimum $k$-cut with a one-paragraph proof. The remaining hard instances have all pair weights below $λ$; for them we prove a merge lemma for Gomory-Hu sides. Finally, we give a 7-vertex graph with a unique Gomory-Hu tree whose unique optimal 3-partition contains no side of that tree, so the first stage of Kapoor's algorithm does not suffice on its own. The main theorem, the 4/3 bound, the merge lemmas and the counterexample are verified in the Lean 4 proof assistant.

0.44

Faster Directed Hopsets, Distance Preservers, and Deterministic Shortcut Sets

cs.DS ·2026-10-08 ·Ben Bals, Daniel Dadush, Gary Hoppenworth, Yasamin Nazari, Rajath Rao K. N
similarity 0.63
Abstract

While there have been many recent advances in getting better tradeoffs for directed distance structures such as hopsets, shortcut sets and distance preservers, most known algorithms are inefficient. In this work we provide three results: - Faster algorithms for directed $(1+ε)$-hopsets, matching the state-of-the-art size/hopbound trade-offs of Bernstein & Wein [SODA23]. Our algorithm is first designed for DAGs and then extended to general graphs (up to $n^{o(1)}$ factors) using the recent DAG projection result of Haeupler, Jiang, and Saranurak [STOC26]. - Faster \textit{deterministic} algorithms for constructing shortcut sets, matching the state-of-the-art size/hopbound tradeoffs of Kogan & Parter [SODA22A]. - Using our improved directed hopset construction, we get significantly faster algorithms for computing source-wise distance preservers. This algorithm is based on speeding-up reductions of Kogan & Parter [SODA22B] by using certain structural properties of our hopsets.

0.29

T-Robinson Spaces: Structure, Recognition, and Applications to Real Data

cs.DM cs.DSmath.CO ·2026-08-21 ·Patricio Asenjo, Sergio Cavero, Mauricio Soto-Gomez, Christopher Thraves Caro
similarity 0.63
Abstract

We study \emph{$T$-Robinson spaces}, a tree-based generalization of Robinson spaces in which every path of a compatible tree induces a Robinson subspace. This framework extends the classical notion of Robinsonian representations from linear orderings to tree structures, allowing the modeling of hierarchical and branching data. We establish a complete combinatorial characterization of $T$-Robinson spaces by proving their equivalence with several graph- and hypergraph-theoretic properties. In particular, we show that a dissimilarity space is $T$-Robinson if and only if all its level graphs are dually chordal with a common compatible tree. Combined with the characterization of hypertrees established by Brucker~\cite{brucker2005hypertrees}, this yields the equivalent characterization in terms of the associated cluster, ball, and 2-ball hypergraphs being hypertrees. Building upon these structural results, we develop a recognition algorithm with complexity \(O(K n^{2})\), where \(K\) denotes the number of minimum spanning trees of the dissimilarity space, improving upon existing hypertree-based approaches whenever \(K\) remains moderate. We further introduce a quantitative measure of $T$-Robinson structure that evaluates the extent to which an arbitrary dissimilarity space admits a tree-like representation. Finally, we discuss applications to real-world datasets, illustrating how $T$-Robinson spaces provide an interpretable framework for analyzing and organizing relational data.

0.17

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

cs.DS ·2026-10-28 ·Arnold Filtser, Gramoz Goranci, Ali Momeni, Neel Patel, Maximilian Probst Gutenberg
similarity 0.63
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.

0.21

Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein

cs.DM cs.CCmath.CO ·2026-10-12 ·Jens Breitung, Timo Gervens, Julius Pörzgen
similarity 0.63
Abstract

We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. Formally, these distances are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise $p$-norms), and local aggregation (operator $p$-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.

0.52

Succinct Representation of Search Trees on Trees

cs.DS ·2026-09-18 ·Seungbum Jo, Nodari Sitchinava
similarity 0.63
Abstract

A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an STT, where the reference tree is a path of totally ordered elements. In this paper, we study the problem of succinct representation of STTs. We consider two cases: (1) general search trees on trees, and (2) Steiner-closed search trees on trees [Bose et al. TALG 2023]. For both cases, we present representations that can be constructed in polynomial time and achieve optimal space up to the lower-order additive terms. We also present data structures for supporting fast traversals of both general and Steiner-closed STTs. For general STTs our data structure still takes optimal space up to lower-order additive terms.

0.20