Space-Optimal Sensitivity Oracles for Single-Source Mincuts

arXiv:2607.00894 · cs.DS · Submitted 2026-07-01 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Space-Optimal Sensitivity Oracles for Single-Source Mincuts".

Jane: Here's the gist of the paper. The paper presents space-optimal data structures for Single-Source Mincut Sensitivity Oracles, focusing primarily on edge failure queries, with a main result being an optimal O(n) space oracle (Theorem 1.1).

Tom: This oracle reports the set of affected vertices whose minimum cut value to the source changes upon the insertion or failure of an edge e in O(n) time.

Jane: The construction leverages intricate connections between the Directed Acyclic Graph (DAG) representation of farthest mincuts to the source (D) and a structure called the Connectivity Carcass.

Tom: The key technical insight is that if an arbitrary (u, s) -mincut U splits a node mu of D, then U D (mu) forms a mu-mincut whose capacity equals c(D (mu)), enabling the use of the connectivity carcass.

Title and authors: Tom: So Jane and I were looking at this paper today by Koustav Bhanja and Merav Parter about "Space-Optimal Sensitivity Oracles for Single-Source Mincuts." It looks like they are tackling the hard problem of finding data structures that can tell you exactly which vertices get affected when an edge fails in a minimum cut calculation.

Jane: Right, so the main thing here is that they’re focusing specifically on edge failure queries, which is harder than just asking about adding a new edge. They claim to have found an optimal space oracle for this, one that uses only O of n space and takes O of n time to report those affected vertices.

Lu: That's the main result from page one where they state their key finding is an optimal O of n space single-source mincut sensitivity oracle for edge failure queries which reports the set of affected vertices in O of n time > <ref:2607.00894#pg1,n space single-source mincut sensitivity oracle for edge failure queries>

Meng: But we always want to know what that actually means for deployment at scale. If you're running a massive network, how does this O of n space structure fit into your operational costs and query latency?

Tom: Exactly. And they aren't just stopping there with the optimal structure; they also provide near-optimal structures with O of n to the power of one point five space, which opens up some other kinds of queries for these systems > <ref:2607.00894#pg2>

Jane: That near-optimal structure supports two main types of queries, one where you check if a single vertex's mincut value changes when an edge fails in log n time, and another where you need to report all the affected vertices in amortized O of log to the power of three time per reported vertex > <ref:2607.00894#pg2>

Lu: The paper details how they build this using something called the Connectivity Carcass and a DAG representation of farthest mincuts, which is a clever way to relate arbitrary mincuts back to simpler structures >

Meng: Relating them back seems like the tricky part. How do you actually use that structure to get that O of n result without it just becoming too slow or too memory hungry in practice?

Tom: They make a key technical insight, which is if an arbitrary mincut splits a node of this DAG, then the intersection of that mincut with something called the connectivity carcass forms another mincut whose capacity equals the capacity of that part of the DAG >

Title and authors: Jane: That sounds like they are using these projections to characterize how things separate in the graph structure, which is crucial for proving their space bound >

Lu: They use a process involving anchors and LCA structures on this farthest mincut DAG, and Lemma six point one establishes that for an arbitrary mincut splitting some node of the DAG, those anchors satisfy specific separation properties > <ref:2607.00894#pg2>

Tom: And they use these anchors to translate edge failure queries into equivalent vertex separation queries on that DAG, which lets them focus only on the relevant nodes and use Lemma nine point three to determine which vertices are reported based on their membership in certain sets > <ref:2607.00894#pg2>

Jane: So, what's the practical implication for someone who just wants to know if a link failure matters for a specific node they care about?

Meng: For that specific query, they say you can check if a vertex's mincut value changes upon edge failure in O of log n time, which is pretty fast >

Tom: That's the one-destination query result. It also mentions insertion queries—checking what happens when you add an edge—which they handle in O of one time, matching the state-of-the-art bounds for that case > <ref:2607.00894#pg1,matching the state-of-the-art bounds for>

Jane: So we have a very compact structure for checking individual vertices and even better speed for adding edges, but what about reporting everything?

Lu: For the output sensitive query, which is reporting all affected vertices between two specific nodes x and y, they provide a structure with O of n to the power of one point five space that supports this in amortized O of log to the power of three time per reported vertex > <ref:2607.00894#pg2>

Meng: That sounds like a big jump from what we usually see for these kinds of queries. What does that near-optimal space complexity actually translate to when you look at running it on real traffic?

Tom: The overall space complexity is dominated by the ancestry and LCA structure in that farthest mincut DAG, which requires O of n to the power of one point five space for those near-optimal structures, but they manage to get down to an optimal O of n space oracle > <ref:2607.00894#pg2>

Jane: So we have this hierarchy: we have the absolute best one with O of n space, and then some near-optimal ones that give us faster query times, which is a good trade-off for many applications >

Title and authors: Lu: The paper's core contribution is showing how the connectivity carcass can be used effectively to characterize separation properties by treating vertices inside each node of the farthest mincut DAG as terminal sets >

Meng: I wonder about the limitations. Where does this work actually stop applying? Does it rely too heavily on having a clean DAG representation of those farthest mincuts in the first place?

Tom: Page two mentions that for insertion queries, they treat things using a nearest mincut tree and the farthest mincut DAG, and failure queries require analyzing how arbitrary mincuts interact with this structure > <ref:2607.00894#pg1>

Jane: That means if you're dealing with a graph where those farthest mincuts are really messy or don't have nice structural properties, this specific machinery might not work as smoothly >

Lu: Also, they mention that the skeleton component alone yields an O of m space oracle, but utilizing projections towards O of n space is what actually gets them to that optimal bound >

Meng: So if I want to deploy this today, is there a simple way to check if the structure itself can handle a graph we have? Because building that DAG representation sounds like it could be computationally expensive upfront >

Tom: The authors are focused on the query time and space efficiency given that you already have those representations, so they aren't solving the initial construction cost problem >

Jane: So to wrap up, this paper, "Space-Optimal Sensitivity Oracles for Single-Source Mincuts," shows we can get down to an optimal O of n space oracle for edge failure queries in O of n time, matching the best known bounds for insertion queries >

Tom: And they also give us near-optimal structures with O of n to the power of one point five space that support fast one-destination and output sensitive queries > <ref:2607.00894#pg2>

Lu: It’s a lot about using projections and anchors to translate edge failure problems into vertex separation problems on the farthest mincut DAG, which is a very specific structural trick >

Meng: For someone running production systems, I’d say the O of n space result is great because it matches existing insertion bounds, but we still need to see how stable this structure is when the underlying graph changes constantly >

Jane: It seems like this research provides a solid foundation for building much more compact tools for analyzing network reliability and sensitivity in dynamic systems, moving us beyond the O of n to the power of two space approaches that were previously standard > <ref:2607.00894#pg1>

The paper's summary: Tom: So we've looked at the mechanics of how they build these structures and what kind of queries they support, and now we need to talk about what this whole paper is actually trying to achieve in plain English >

Jane: Okay, so basically, this paper is about finding the smallest possible amount of memory needed for a data structure that can tell you which part of a network changes when you break one connection >

Tom: Exactly. The main achievement here is they found an optimal space oracle for edge failure queries, and they claim it only needs O of n space to report those affected vertices in O of n time >

Jane: That’s huge because before this, we thought these kinds of sensitivity queries would require way more memory, maybe even something like O of n to the power of two >

Tom: Right. And they prove this is the best possible bound for that specific query type, which matches what they already had for adding a new edge >

Lu: The paper uses a clever trick involving something called the connectivity carcass and how it relates to a DAG representation of farthest mincuts to the source >

Jane: That sounds like a complicated way of saying they’re using structural properties of the graph to simplify the problem so they don't have to check every possible cut >

Tom: It's about using these projections to characterize separation properties, which lets them use anchors and LCA structures on that farthest mincut DAG >

Jane: And those anchors help them translate the edge failure query into a vertex separation query on that DAG, which is a much more manageable problem for their structure >

Lu: They show that by treating vertices inside each node of the farthest mincut DAG as terminal sets, you can effectively characterize how things separate in this way >

Tom: So what does this mean practically? If you’re running a system where edges fail constantly, this structure lets you figure out the impact without needing massive amounts of memory to store everything >

Jane: It means for dynamic systems, we can get these sensitivity reports much faster and with less memory than previously thought >

Lu: But they also provide near-optimal structures with O of n to the power of one point five space that support other types of queries, like checking if a single vertex's value changes in log n time >

Tom: So we have two tiers here. You get the absolute best for edge failure reporting with O of n space and O of n time, and then you get these near-optimal structures for faster individual checks or reporting sets between specific points >

Jane: It’s a hierarchy, but it moves us beyond those older approaches where everything required exponential space in terms of the number of nodes in the graph >

Lu: The core idea is that by focusing on how mincuts split specific points in the farthest mincut DAG, you can characterize separation properties that were previously hard to track >

Tom: So for production, this suggests a way to build much more compact tools for analyzing network reliability and sensitivity in dynamic systems >

The paper's improvements: Tom: So we've talked about the main result—that O of n space oracle for edge failure queries—and now we need to hear what they’re suggesting next to push those bounds even further >

Jane: Right, so they aren't just happy with that O of n space result; they are proposing improvements for other kinds of sensitivity queries as well >

Tom: They suggest a way to get near-optimal query times using an O of n to the power of one point five space structure that supports one-destination queries in log n time and output sensitive queries in amortized log to the power of three time per reported vertex >

Jane: That means for those specific checks on single vertices, you get a speed boost, and for reporting groups of affected vertices, it’s much more efficient than what we had before >

Lu: They also propose extending this work to support all-pairs mincut sensitivity queries with an O of n to the power of two space structure that reports all pairs between which the mincut value decreases in amortized log to the power of three time per pair >

Tom: So, they are essentially showing us a ladder: you have the absolute best one for edge failures, then these near-optimal structures for faster specific queries, and finally an even larger structure for reporting pairs >

Jane: The implication here is that we can tailor the memory usage to exactly what query you need—if you only care about one vertex, you use less space than if you want to report everything >

Lu: They also have a proposal for a better way to handle the underlying farthest mincut DAG itself, suggesting an O of n to the power of one point five space structure for that DAG that supports constant time ancestry queries and log n time LCA queries >

Tom: That’s interesting because building that DAG representation upfront sounds expensive, so if you can build it with less space and still get fast LCA on it, that makes the whole system much cheaper to maintain >

Jane: And they talk about how using anchors for query translation could make those edge failure queries even faster by focusing only on the relevant nodes in the DAG >

Lu: The core idea is moving away from just having a big structure and instead using projections and anchors to translate the problem into a smaller, more manageable one >

Tom: It sounds like they are making it much smarter than just building one monolithic structure for every possible query type >

Conclusion: Tom: So we’re wrapping up this look at "Space-Optimal Sensitivity Oracles for Single-Source Mincuts," and we need to summarize where this leaves things >

Jane: Basically, the paper shows that you can build a really compact data structure using only O of n space to answer edge failure queries in O of n time >

Tom: That’s the main win, matching the best known bounds for adding an edge, and they also give us these near-optimal structures with O of n to the power of one point five space that support faster single vertex checks >

Lu: And they even propose a way to build that farthest mincut DAG itself more efficiently, using O of n to the power of one point five space for ancestry and LCA queries >

Meng: From an engineering standpoint, this is good because it means we could potentially deploy these sensitivity tools in systems where memory is tight, like on edge devices >

Jane: It also gives us a roadmap for improving those near-optimal query times, showing how you can push from log to the power of three for output sensitive queries >

Tom: It’s a lot about using projections and anchors to turn these complicated network problems into simpler separation questions on that DAG structure >

Lu: They are basically saying the key is exploiting the specific geometry of those farthest mincut DAGs through things like connectivity carcass projections >

Jane: So for anyone working on dynamic networks or reliability analysis, this paper gives you a much more compact way to figure out how sensitive your network is to a single link failure >

Tom: It’s solid work because the results are tied directly to the actual space and time complexity numbers, not just some theoretical idea >

Lu: I think the most important thing is that it validates treating vertices inside those DAG nodes as terminal sets, which simplifies the proof structure for these separation properties >

Jane: So moving forward, we'll see if other researchers can build on this foundation to tackle even more complex network topologies or different types of cut problems >

Weizmann Institute of Science, Israel

cs.DS

Submitted: 2026-07-01

Updated: 2026-11-05

Comments: fixed and improved output-sensitive query

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 95/100

The gist: The paper presents space-optimal data structures for Single-Source Mincut Sensitivity Oracles, focusing primarily on edge failure queries…

Key concepts

Connectivity Carcass
This structure is used to analyze how an arbitrary minimum cut interacts with the Directed Acyclic Graph (DAG) of farthest mincuts. If a cut splits a node in this DAG, the intersection with the DAG's downward paths forms a specific type of minimum cut, allowing for efficient analysis and establishing optimal space bounds.
Farthest Min-Cut DAG (D)
This is a graph representation derived from finding minimum cuts from the source to all other vertices. The structure of this DAG is crucial because it allows the paper to characterize separation properties of mincuts. Certain properties of mincuts are linked directly to how they partition the nodes within this specific DAG.
Anchors and LCA Translation
Anchors are specific points associated with vertices $x$ and $y$ relative to their Lowest Common Ancestor (LCA) in the Farthest Min-Cut DAG. By using these anchors, the paper translates complex edge failure queries into simpler vertex separation queries on the DAG, significantly reducing query time by focusing only on relevant parts of the structure.

Terminology

Summary

The paper presents space-optimal data structures for Single-Source Mincut Sensitivity Oracles, focusing primarily on edge failure queries, with a main result being an optimal O(n) space oracle (Theorem 1. p. 2

Where the paper says it

Space Optimal Oracle. Our main result shows that compact single-source mincut sensitivity oracles of just O(n) space can also be achieved for edge failure queries: Theorem 1.

1). This oracle reports the set of affected vertices whose minimum cut value to the source changes upon the insertion or failure of an edge e in O(n) time. p. 0
Where the paper says it

We study Single-Source Mincut Sensitivity Oracles: compact data structures that, when queried with an edge e, report those affected vertices whose mincut value to s changes upon the insertion or failure of e. Insertion queries were treated by Baswana, Gupta, and Knollmann [Algorithmica ’22], who showed an extremely compact oracle with only O(n) space.

The construction leverages intricate connections between the Directed Acyclic Graph (DAG) representation of farthest mincuts to the source (D) and a structure called the Connectivity Carcass. p. 2

Where the paper says it

They showed an O(n) space oracle for edge insertions in the single-source setting: Given any inserted edge, it can determine all of the vertices whose mincut value to the distinguished source s is affected by the insertion. Their central structural insight is an O(n) space representation for the family of farthest mincuts to s, called the Farthest Mincut DAG (directed acyclic graph); we briefly overview it in Section 3.

The key technical insight is that if an arbitrary (u, s) -mincut U splits a node mu of D, then U D (mu) forms a mu-mincut whose capacity equals c(D (mu)), enabling the use of the connectivity carcass. p. 8
Where the paper says it

2 Key Insight: The Bridge to the Carcass We now present the key insight that underlies our approach. The idea is to analyze how arbitrary mincuts to the source vertex s “interact” with the farthest mincut DAG D.

This machinery is crucial for establishing the optimal space bound. p. 2
Where the paper says it

However, one can hope for a better output-sensitive query time, as we will discuss shortly. The space is optimal even for the fixed-pair setting, and even in simple graphs: this easy information-theoretic space lower bound appears in Section D.

Near-optimal query time oracles with O(n 1. p. 0

Where the paper says it

It reports the set of affected vertices in O(n) time, thus matching the state-of-the-art bounds for the insertion case. • Additionally, we provide oracles with near-optimal query times at the cost of increasing the space to O(n 1.

5) space are also provided (Theorem 1. p. 2
Where the paper says it

The “brute-force” approach to handle failure queries in the single-source setting is to store n − 1 oracles of [PQ80], one for every pair in {s} × V \ {s}. A more sophisticated oracle of O(n 2 ) space, which in fact works for the most general all-pairs setting, was provided by [BP22], but this does not improve over the brute-force for the single-source case.

2). These structures support two main types of queries:

  1. One-Destination Query: Determining if a vertex u 's mincut value changes upon edge failure in O(n) time, or insertion in O(1) time.

  2. Output-Sensitive Query: Reporting all affected vertices in amortized O(cubed n) time per reported vertex.

The paper details several tools:

  • From Insertion to Failure: Insertion queries are related to representing Near(u, s) and Far(u, s) using a nearest mincut tree T and the farthest mincut DAG D. Failure queries are addressed by analyzing how arbitrary mincuts interact with D, aiming to report vertices that separate two specific vertices. p. 8

    Where the paper says it

    8 These two LCAs can be easily found in O(n) time, and as discussed, all the non-trivial nodes are ancestors of (at least) one of them. Therefore, our goal becomes to give a data structure for the following query: (Q) Given e = {x, y} ∈ E and LCA µ of D(x), D(y), report all vertices u ∈ D↑ (µ) that separate x, y.

  • Key Insight: The Bridge to the Carcass: As mentioned, utilizing the connectivity carcass projections allows for characterization of separation properties.

  • Utilizing Skeletons for Space Bounds: The skeleton component alone yields an O(m) space oracle, and utilizing projections towards O(n) space is what achieves the optimal bound.

  • Anchors and Query Translation: The query translation process employs anchors (z x, z y) of vertices x and y with respect to an LCA mu of D(x), D(y). Lemma 6.1 establishes that for a (u, s) -mincut U splitting mu, the anchors satisfy specific separation properties. p. 1

    Where the paper says it

    5 Organization . 11 4 Carcass Tools 12 5 The Representatives Framework 14 6 Anchors and Query Translation 17 7 Mincuts Splitting the LCA 19 7.

  • Mincuts Splitting the LCA: The data structure for Query (Q1) is built using a representative framework to analyze subpaths of pi mu(e) and apply Lemma 9.3 to determine which vertices are reported based on their membership in sets A mu(z x) or A mu(z y). p. 3

    Where the paper says it

    In our view, one of the central conceptual contributions of this paper is in demonstrating how the connectivity carcass can be effectively and neatly utilized for a problem which, on the face of it, seems to have little to do with terminal sets and Steiner mincuts. Surprisingly, the key to our solution is treating the vertices inside each node in the farthest mincut DAG as a terminal set.

  • Data Structures for Fast Queries: The O(n 1.5) space structure supports the output-sensitive query (Theorem 1. p. 4

    Where the paper says it

    Thus, our Theorem 1. 2(2) is the first to achieve near-optimal output-sensitive query time for edge failure queries in the all-pairs setting; for edge insertion queries, [BGK22] gave O(n 2 ) space with optimal output-sensitive time.

    2, Item 2), reporting all vertices separating x and y in O(X cubed n) time. p. 3
    Where the paper says it

    As an almost-immediate corollary of Theorem 1. 2(2), we get the following result in all-pairs setting2 : 1More accurately, the improvement would be to Item 2 of Theorem 1.

The overall space complexity is dominated by the ancestry/LCA structure in D, requiring O(n 1. p. 1

Where the paper says it

27 9 Data Structures for Fast Queries: Output-Sensitive and One-Destination 28 9. 1 Ancestry and LCA in Farthest Mincut DAG .

5) space for the near-optimal structures, while the optimal oracle achieves O(n) space. p. 3
Where the paper says it

Near-Optimal Query Time. We complement our optimal space-oracle of Theorem 1.

The time complexity for Query (Q1) is O(X n + cubed n), and for Query (Q2), it is O(n). p. 0
Where the paper says it

It reports the set of affected vertices in O(n) time, thus matching the state-of-the-art bounds for the insertion case. • Additionally, we provide oracles with near-optimal query times at the cost of increasing the space to O(n 1.

The paper's core contribution lies in demonstrating how the connectivity carcass can be effectively utilized for a problem seemingly unrelated to terminal sets and Steiner mincuts by treating vertices inside each node of the farthest mincut DAG as a terminal set. The key technical machinery involves using the connectivity carcass projections to characterize separation properties, leading to an O(n) space oracle. p. 7

Where the paper says it

Next, we introduce the key connecting link between the farthest mincut DAG and the connectivity carcass. Based on this link, we first discuss how the simpler skeleton component alone can yield a non-trivial O(m) space oracle with O(n) query time.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Optimizing Sensitivity Oracle Construction for Edge Failure Queries: The system can construct an O(n) space data structure that reports all affected vertices whose mincut value to s decreases upon failure of an edge e in O(n) time, matching the state-of-the-art bounds for insertion queries.

  2. Achieving Near Optimal Query Times with Subquadratic Space: The system can utilize an O(n 1.5) space data structure to support one-destination queries in O(log n) time and output-sensitive queries in amortized O(log3 n) time per reported vertex, which were previously unknown even for insertion cases.

  3. Supporting All-Pairs Mincut Sensitivity Queries: The system can be extended to an O(n 2.5) space structure to report all pairs of vertices between which the mincut value decreases upon failure of an edge in amortized O(log3 n) time per pair, improving upon existing O(n 2) space bounds for this query type.

  4. Enabling Fast Ancestry and LCA Queries on Farthest Mincut DAG: The system incorporates an O(n 1.5) space data structure for the farthest mincut DAG D that supports O(1) time ancestry queries and O(log n) time LCA queries, leveraging Lemma 3.2 to bypass the Reachability Conjecture worst-case space requirements.

  5. Efficient Query Translation via Anchors: The system implements an anchor translation strategy that allows it to translate edge failure queries into equivalent vertex separation queries on the farthest mincut DAG D, reducing query complexity by focusing only on relevant nodes and leveraging the structural properties of LCAs in D.

Abstract

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; 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(n) membership queries or amortized O(squared 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.

Sources

Related papers