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.
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.