Optimal compact structure encodes all pairs nearest minimum cuts
An Optimal Structure for All-Pairs Nearest Mincuts and Sensitivity Oracles for Edge Insertions
Data Structures and Algorithms
Summary
In a network, it’s useful to know the smallest way to separate any two points by cutting connections. There is a neat tree structure called the Gomory-Hu tree that stores one minimum cut for every pair of points using only a little space. This paper asks if a similarly small structure can store a special kind of minimum cut, called the nearest minimum cut, for all pairs. The authors show it can be done in the same optimal space and give a way to find these cuts efficiently. They also build a tool that quickly tells how adding a connection changes these minimum cuts for all point pairs.
What this means in practice
- •For network engineers: Detect changes in network reliability efficiently after adding connections by quickly updating minimum separation points for all node pairs.
- •For infrastructure planners: Analyze fault tolerance of transportation or power systems by compactly storing critical links whose failure separates important points.
Authors
Koustav Bhanja, Yotam Kenneth-Mordoch, Asaf Petruschka
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].