How much information is needed to describe the effect of any single edge failure on all mincuts? Classical mincut representations, such as Gomory-Hu trees and cactus-like structures, show that mincuts often admit unexpectedly compact static certificates. However, much less is known about whether such compactness survives failures. We study the single-source setting. Given an undirected multigraph $G$ and source $s$, our oracle reports, for any failed edge $e$, all vertices $t$ whose $s,t$-mincut value decreases in $G\setminus{e}$; equivalently, whether $e$ belongs to some $s,t$-mincut. This is the single-source analogue of Picard-Queyranne's fixed-pair [MPS '80] and Baswana-Pandey's all-pairs sensitivity results [SODA '22], and the failure counterpart of Baswana-Gupta-Knollmann's insertion oracle [Algorithmica '22]. No subquadratic-space solution was known to date. We give an optimal $O(n)$-space oracle with $O(n)$ reporting time, matching the insertion bounds. We also give $O(n^{1.5})$-space oracles for insertions and failures, with $O(\log n)$ membership queries or amortized $O(\log^2 n)$ reporting time per affected vertex. Subquadratic-space oracles with such fast query times were unknown, even for insertions. Our main technical contribution connects farthest mincut DAGs, central to the insertion oracle, with Dinitz-Vainshtein's Connectivity Carcass for Steiner mincuts [STOC '94], which generalizes global-mincut cactus representations. These novel, intricate connections reveal the carcass's potential beyond Steiner mincuts.
Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space
Merav Parter, Elad Tzalik
AI 速览：作者提出首个在失败集大小不受限时使用次二次空间的确定性容错连通性预言机，并给出确定性与随机化预言机之间的首个多项式分离。
A fault-tolerant (FT) connectivity oracle for an $n$-vertex graph $G=(V,E)$ determines whether $G- F$ is connected for any query set $F\subseteq E$. When the number of failures is unrestricted, prior constructions exhibited a sharp contrast between randomization and determinism: randomized oracles use only $\widetilde{O}(n)$ space [Duan and Pettie, SICOMP 2020], whereas no deterministic construction was known to improve upon storing $G$ explicitly, requiring $Θ(n^2)$ bits in the worst case. The promise that $F\subseteq E$ is essential for subquadratic space: allowing arbitrary queries $F\subseteq V\times V$ forces quadratic space. For queries containing at most $f$ failures, Khanna, Konrad, and Putterman [SODA 2027] recently constructed deterministic oracles using $\widetilde{O}(\sqrt{f}n)$ space that also report approximate distances with polylogarithmic stretch. Their result improves upon the classical $O(fn)$ space bound for deterministic connectivity oracles [Pătraşcu and Thorup, FOCS 2007], but offers no space savings over storing $G$ when $f=Θ(n^2)$. We present the first deterministic connectivity oracles with subquadratic space for failure sets of unrestricted size, using $\widetilde{O}(n^{7/4})$ space. We also establish the first polynomial separation between deterministic and randomized connectivity oracles, proving that every deterministic oracle requires $\widetildeΩ(n^{3/2})$ bits in the worst case. For queries containing at most $f$ failures, we obtain deterministic connectivity oracles using $\widetilde{O}(f^{2/5}n)$ space, improving the dependence on $f$ in the bound of Khanna et al., and prove a lower bound of $\widetildeΩ(f^{1/4}n)$ bits.
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.