1 Introduction↩︎

Minimum cuts, or mincuts for short, are among the most ubiquitous concepts in graph theory and algorithms. Let \(G=(V,E)\) be an undirected multi-graph on \(n\) vertices and \(m\) edges. A minimum cut between a pair of vertices \(u,v \in V\), denoted \(u,v\)-mincut, is a set of edges of least cardinality whose removal disconnects \(u\) from \(v\). Compact representations and data structures for mincuts have been a major field of research. A prime example is the celebrated Gomory-Hu Tree [1], a compact tree structure of only \(O(n)\) space, that represents at least one \(u,v\)-mincut for every pair of vertices \(u,v\in V\). However, in many real-world settings, a basic static network undergoes small and commonly transient changes, such as temporary link failures. This motivates the vast practical and theoretical study of sensitivity oracles: compact data structures that can effectively report the new solution for a given graph problem once such a change occurs.

Sensitivity oracles for mincuts were first introduced by Picard and Queyranne in 1980 [2], and substantial advancement on them has been made in recent years [3]–[10]; here we only focus on results pertaining to undirected multi-graphs, which are most relevant to our context. The original setting considered by Picard and Queyranne was of a fixed pair of vertices \(s,t\), and showed an \(O(n)\) space structure that can determine whether the \(s,t\)-mincut value changes upon the failure (i.e., the deletion) or the insertion of any given edge. Recently, Bhanja [9] has shown that the oracle of [2] is tight in a very strong sense: an oracle that can support queries of two (or more) failing edges already requires (information-theoretically) \(\Omega(n^2)\) space. However, there remains a different intriguing avenue for improvement: going beyond a fixed “source-destination” pair of vertices.

The first result in this direction was by Baswana, Gupta, and Knollmann [3]. 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 3. However, their work did not address the arguably more important edge failure queries, which are considerably harder. Essentially, this is because supporting insertion queries reduces to efficient representations of only at most \(2(n-1)\) mincuts to the source (the nearest one and the farthest one from each vertex), while failure queries deal with all the mincuts to the source, whose number can be exponential. The “brute-force” approach to handle failure queries in the single-source setting is to store \(n-1\) oracles of [2], one for every pair in \(\{s\} \times V\setminus\{s\}\). A more sophisticated oracle of \(O(n^2)\) space, which in fact works for the most general all-pairs setting, was provided by [4], but this does not improve over the brute-force for the single-source case.

1.0.0.1 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:

Both the space and query time in 1 precisely match those of [3] for edge insertion queries. The query time is “worst-case optimal”, as there exist graphs (say a cycle) where failure of an edge can affect the mincuts to \(s\) of \(\Omega(n)\) vertices. 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 13.

Our oracle is obtained via intricate usage of the Connectivity Carcass [11]–[14]. The carcass, first announced by Dinitz and Vainshtein in 1994, is a data structure that compactly represents all Steiner mincuts of a given terminal set \(S \subseteq V\) — a Steiner mincut is one with minimum value among those cuts that separate at least one pair of terminals. However, this description barely conveys its complex interface, which unfortunately cannot be compressed into one short “blackbox” result. We do our best to provide a clean and succinct interface in 2.1, but it is nevertheless quite dense. Moreover, the inner workings of the carcass are also highly complicated. Only very recently, more than two decades after its original announcement, Baswana and Pandey [14] provided the first complete and formal treatment of this structure. Perhaps for these reasons, the full potential of the carcass for algorithmic applications seems relatively unexplored. The few existing applications [4], [9], [12] employ it in contexts where Steiner mincuts are either the main focus themselves, or of rather immediate relevance.

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. In each such node, we embed carefully chosen components of the corresponding carcass. These are utilized through a machinery that “translates” between the global view of mincuts to the source \(s\), through the DAG, and into the local views of the carcasses inside the nodes. This high-level intuition is explained in detail in the Technical Overview (3).

1.0.0.2 Near-Optimal Query Time.

We complement our optimal space-oracle of 1 with a larger but still subquadratic \(O(n^{1.5})\) space oracle, whose query time guarantees are optimal up to logarithmic factors:

Near-optimal query complexities as above were not previously achieved, even for just edge insertion queries, by any oracle with \(o(n^2)\) space. It turns out that the key for these lies in supporting fast reachability queries in the farthest mincut DAG of [3]. In general, answering reachability queries in a DAG is believed to be inherently hard: the Reachability Conjecture [15], [16] states that reachability oracles for DAGs on \(n\) vertices and \(m\) edges require \(\tilde{\Omega}(n^2)\) space to achieve \(o(m)\) time queries, in the worst case.

Interestingly, the nice structural properties of farthest mincuts are “inherited” by their representing DAG, endowing it with a special structure. We show that this can be exploited to bypass the conjectured worst-case hardness, allowing us to design an \(O(n^{1.5})\) space oracle for constant time reachability queries. Combining this main ingredient with some more technical embellishments to the oracle of 1 results in the above 2. Moreover, the reachability oracle is the only “heavy” component: any improvement to its space would immediately yield the same improvement⁴ to 2. However, our approach seems hard to improve beyond \(O(n^{1.5})\) space; it would be very interesting if one could find a more compact oracle for reachability in the farthest mincut DAG, or provide evidence for hardness.

As an almost-immediate corollary of 2([item:faster-queries-reporting-all]), we get the following result in all-pairs setting⁵:

We note that [4] stated an \(O(n^2)\) space oracle that reports all affected pairs by an edge failure in amortized \(O(1)\) time per pair. However, this specific statement seems inaccurate as their query time incurs an additive \(O(n)\) term (private communication with S. Baswana, 2026). Thus, our 2([item:faster-queries-reporting-all]) is the first to achieve near-optimal output-sensitive query time for edge failure queries in the all-pairs setting; for edge insertion queries, [3] gave \(O(n^2)\) space with optimal output-sensitive time.

1.0.0.3 Related Works.

We give a broader view of sensitivity oracles through the lens of closely related and central topics of dynamic algorithms and sparsifiers for mincuts. The dynamic algorithms aim to maintain information of mincuts where the graph changes over time due to edge updates (insertion/deletion). There exist many efficient partial/fully dynamic algorithms for fixed-pair mincuts [17]–[19] and global mincuts [20]–[22]. However, the first and only nontrivial algorithm for dynamically maintaining a Gomory-Hu tree (or all-pairs mincuts) was established very recently by Kenneth-Mordoch and Krauthgamer [23]. They design an algorithm that uses \(O(n^{1.5})\) space and achieves \(O(n^{1.5})\) update time. Their techniques are mostly based on the friendly cut sparsifier of [24], which is inherently restricted to unweighted simple graphs (without parallel edges). Also, there exist graph instances for which any such friendly cut sparsifier must occupy \(\Omega(n^{1.5})\) space. It is now interesting to explore whether this bottleneck can be broken to achieve better bounds, where our approach might turn out to be useful.

Sparsification, in general, is a powerful tool that helps us preserve properties of a graph in a relatively much smaller graph. Several classical sparsifiers for mincuts (or cuts in general) have been developed that sparsify the graph while the relevant cuts can be preserved approximately [25]–[27] or exactly [1], [24], [28], [29]. The space occupied by the exact mincut sparsifiers preserving all mincuts between every vertex pair [23], [28] is parameterized on the value \(\omega\) which is the maximum value of any \(s,t\)-mincut over all \(s,t \in V\), and they can achieve \(O(n)\) space only when \(\omega\) is constant.

1.0.0.4 Future Directions.

A natural next step is to extend our results to the all-pairs setting. An intriguing open problem is whether one can obtain an \(O(n)\) space sensitivity oracle for all-pairs mincuts. Our results for the single-source setting seem to provide evidence in this direction, especially in light of recent efficient algorithmic reductions from all-pairs to single-source mincuts, e.g., in [30]–[32].

Another direction is weighted edge failures. In a sense, our oracles do work for weighted graphs: 1 gives an \(O(n)\) space data structure that, given an edge \(e \in E\), can determine all the vertices \(u\) such that \(e\) contributes to some \(u,s\)-mincut (and 2 works similarly). So, in the weighted setting, our “edge failure” query translates to determining whether the \(u,s\)-mincut value changes when the capacity (i.e., weight) of the edge is reduced by some \(\Delta \in (0,1]\) (assuming, by scaling, that weights are integral). Extending our oracles to handle a weighted edge failure which reduces its capacity to zero (or more generally, by an arbitrary amount) remains an interesting challenge. This is particularly intriguing as Baswana and Bhanja [6] recently extended the fixed-pair oracle of [2] to this weighted setting.

2 Preliminaries↩︎

Throughout, we consider an unweighted, undirected, connected multi-graph \(G = (V,E)\) with \(n = |V|\) vertices and \(m = |E|\) edges, which has a designated source vertex \(s \in V\).

For \(A \subseteq V\), the capacity \(c(A)\) is the number of edges crossing from \(A\) to \(\overline{A} := V\setminus A\). Those edges are called the edge-set of the cut \(A\), or the contributing edges of \(A\). If \(\emptyset \neq X \subseteq A\) and \(\emptyset \neq Y \subseteq \overline{A}\), we say that \(A\) is an \((X,Y)\)-cut. An \((X,Y)\)-cut of smallest capacity is called \((X,Y)\)-mincut. The term \(X,Y\)-(min)cut refers to either an \((X,Y)\)-(min)cut or a \((Y,X)\)-(min)cut. When \(X,Y\) are singletons \(X=\{x\}\) and \(Y=\{y\}\), we may write \(x,y\)-(min)cut, and such shorthands for singletons apply to other notations as well. For \(S \subseteq V\), the (cut defined by) \(A\) is said to be an \(S\)-cut or a Steiner cut for \(S\) if \(S \cap A \neq \emptyset\) and \(S \cap \overline{A} \neq \emptyset\). An \(S\)-cut of smallest capacity is called \(S\)-mincut or a Steiner mincut for \(S\), and its capacity is denoted by \(\lambda_S\).

It is well-known that \(c(\cdot)\) satisfies submodularity: \(c(A) + c(B) \geq c(A \cap B) + c(A \cup B)\) for all \(A,B \subseteq V\). As \(G\) is undirected, this also implies posimodularity: \(c(A) + c(B) \geq c(A \setminus B) + c(B \setminus A)\) for all \(A,B \subseteq V\). Rather than using these inequalities directly, we will use their consequence on mincuts:

Results of very similar flavor to 1 have been widely observed, e.g.in [2], [3], [5], [13], [29]. We give the short proof in 11. By submodularity, one sees that if \(A\) and \(B\) are both \((X,Y)\)-mincuts, then so are \(A \cap B\) and \(A \cup B\). This allows us to define farthest and nearest mincuts:

Another lemma along these lines is concerned with three mincuts to the source \(s\). Again, this lemma has been essentially observed before, e.g.in [3], [13], [14], [33]. See 11 for the proof.

2.1 Essentials of the Connectivity Carcass↩︎

Here, we succinctly present the “must-knows” of the seminal Connectivity Carcass [11]–[13]. The carcass is a rich and complex structure; we strongly recommend referring to [14] for a simplified and comprehensive presentation. Our terminology differs slightly from theirs, mainly since we bypass the flesh component of the carcass. See 10.1 for an example demonstrating the carcass.

Let \(S \subseteq V\) be a distinguished set of vertices called terminals. Two vertices \(u,v \in V\) are \(S\)-equivalent if no \(S\)-mincut keeps \(u\) and \(v\) on different sides. We give unique identifiers to the \(S\)-equivalence classes, and denote by \(\phi_S (u)\) the identifier of \(u\)’s class, so \(\phi_S (u) = \phi_S (v)\) iff \(u,v\) are \(S\)-equivalent.

A partition of \(S\) into \(S_1,S_2\) is called a valid partition if there is some \(S\)-mincut \(C\) s.t.\(C \cap S = S_1\) and \(\overline{C} \cap S = S_2\), or equivalently if any \(S_1,S_2\)-mincut is an \(S\)-mincut. For a valid partition \(S_1,S_2\), we say that:

• \(S_1,S_2\) distinguishes edge \(e \in E\) if there exists an \(S_1,S_2\)-mincut to which \(e\) is contributing.

• \(S_1,S_2\) distinguishes vertex \(v \in V\) if there exists two \(S_1,S_2\)-mincuts, one keeping \(v\) on the side of \(S_1\), and the other keeping \(v\) on the side of \(S_2\).

Vertex \(v \in V\) is called stretched (w.r.t.\(S\)) if \(v\) is distinguished by some valid partition of \(S\), and non-stretched otherwise. All terminals are non-stretched, but a non-stretched vertex need not be a terminal.

The carcass is based on a cactus graph and related notions defined as follows:

The skeleton is a cactus that compactly stores all valid partitions (see [14]).

A canonical cut in \(\mathcal{H}_S\) is said to distinguish a vertex/edge if its corresponding valid partition distinguishes it. The projection mapping extends \(\pi_S (\cdot)\) to non-terminals and to edges, and provides a characterization of those canonical cuts distinguishing them (see [14]).

3 Technical Overview↩︎

We give a technical overview focusing on our main result, 1, structured as follows. We first explain the edge insertion oracle of [3], who introduced the farthest mincut DAG, and provide some basic insights towards supporting failure queries. 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. Finally, we let carcass projections into the picture, and explain how these are used to obtain the \(O(n)\) space oracle.

3.1 From Insertion to Failure↩︎

Our starting point is the single-source mincuts oracle for edge insertion by [3]. Observe that insertion of edge \(e\) changes the \(u,s\)-mincut value if and only if \(e\) contributes to \(\mathsf{Near}(u,s)\) and to \(\mathsf{Far}(u,s)\). Thus, the problem reduces to efficiently representing \(\mathcal{N} = \{\mathsf{Near}(u,s)\}_{u \in V \setminus \{s\}}\) and \(\mathcal{F} = \{\mathsf{Far}(u,s)\}_{u \in V \setminus \{s\}}\).

Using sub/posimodularity, it is not hard to show that \(\mathcal{N}\) is a laminar family, and thus admits an \(O(n)\) size representation called the nearest mincut tree \(\mathcal{T}\): its nodes form a partition of \(V\) (where the root contains only \(s\)), such that, for each \(u \in V \setminus \{s\}\), \(\mathsf{Near}(u,s)\) has precisely those vertices found in descendants of the node containing \(u\). While \(\mathcal{F}\) may not be laminar, the central contribution of [3] was showing that it admits an analogous representation: the farthest mincut DAG \(\mathcal{D}\), stated in [thm:32baswana32et32al32DAG] below. Throughout the paper, we use ‘tree terminology’ for DAGs: the in-neighbors and out-neighbors of a node are its parents and children, respectively; its descendants are those nodes reachable from it, and its ancestors are those that can reach it; a strict ancestor/descendant is one that is not the node itself.

For each structure \(\mathcal{S} \in \{\mathcal{T}, \mathcal{D}\}\), let \(\mathcal{S}(u)\) be the node of \(\mathcal{S}\) that contains \(u\), \(\mathcal{S}^{\uparrow}(u)\) be the set of vertices in ancestors of \(\mathcal{S}(u)\), and \(\mathcal{S}_{\downarrow}(u)\) be the set of vertices in descendants of \(\mathcal{S}(u)\). So, for every \(u,w \in V \setminus \{s\}\), \[w \in \mathsf{Near}(u,s) \Leftrightarrow w \in \mathcal{T}_{\downarrow}(u) \Leftrightarrow u \in \mathcal{T}^{\uparrow}(w) \quad \text{and} \quad w \in \mathsf{Far}(u,s) \Leftrightarrow w \in \mathcal{D}_{\downarrow}(u) \Leftrightarrow u \in \mathcal{D}^{\uparrow}(w).\] See 10.2 for an example demonstrating \(\mathcal{T}\) and \(\mathcal{D}\). Thus, when edge \(e = \{x,y\}\) is inserted, the set of vertices \(u\) such that \(e\) contributes to \(\mathsf{Near}(u,s)\) and to \(\mathsf{Far}(u,s)\) is precisely \(\mathcal{T}^{\uparrow}(x) \setminus \mathcal{D}^{\uparrow}(y) \cup \mathcal{T}^{\uparrow}(y) \setminus \mathcal{D}^{\uparrow}(x)\), i.e., each \(u\) having \(x\) as a descendant in \(\mathcal{T}\) (so, \(x\in \mathsf{Near}(u,s)\)) and \(y\) not a descendant in \(\mathcal{D}\) (so, \(y\notin \mathsf{Far}(u,s)\)), or vice versa. Hence, the data structure of [3] simply stores \(\mathcal{T}\) and \(\mathcal{D}\), and answers an insertion query in \(O(n)\) time by \(O(1)\) BFS searches in (the reverses of) \(\mathcal{T}\) and \(\mathcal{D}\).

Given this background, we move on to consider the problem of 1: supporting a failure query of edge \(e = \{x,y\} \in E\). Observe that the failure of \(e\) changes the \(u,s\)-mincut value if and only if \(e\) contributes to some \(u,s\)-mincut. This makes the failure variant a lot more challenging than the insertion one, which just requires examining \(\mathsf{Near}(u,s)\) and \(\mathsf{Far}(u,s)\), only two very special \(u,s\)-mincuts. In light of this, it might seem that the nearest mincut tree \(\mathcal{T}\) and farthest mincut DAG \(\mathcal{D}\) have little to do with our task. While \(\mathcal{T}\) is indeed less relevant, it turns out that \(\mathcal{D}\) is useful also for failure queries, as explained next.

3.1.0.1 Utilizing Ancestry Structure.

A vertex \(u\) is said to separate two non-empty vertex subsets \(P,Q \subseteq V\) if there exists a \(u,s\)-mincut that keeps \(P\) and \(Q\) on different sides. Hence, the goal in a failure query of an edge \(e = \{x,y\} \in E\) is to report all vertices that separate \(x,y\).⁹ We now give a few basic observations on where these vertices lie in \(\mathcal{T}\) and in \(\mathcal{D}\), which help in answering our query, and also highlight what makes the latter more useful. For each \(\mathcal{S} \in \{\mathcal{T}, \mathcal{D}\}\), let us classify the nodes into three types based on their ancestry relations to the nodes of \(x\) and \(y\):

Common ancestor:

an ancestor of both \(\mathcal{S}(x)\) and \(\mathcal{S}(y)\).

Exclusive ancestor:

an ancestor of exactly one of \(\mathcal{S}(x)\) or \(\mathcal{S}(y)\).

Non-ancestor:

neither an ancestor \(\mathcal{S}(x)\), nor of \(\mathcal{S}(y)\).

Exclusive ancestors are trivial to handle both in \(\mathcal{T}\) and in \(\mathcal{D}\): all their vertices separate \(x,y\). Indeed, if \(\mathcal{T}(u)\) (resp., \(\mathcal{D}(u)\)) is an exclusive ancestor, then the \(u,s\)-mincut \(\mathsf{Near}(u,s)\) (resp., \(\mathsf{Far}(u,s)\)) keeps \(x\) and \(y\) on different sides. The other two types play dual roles in \(\mathcal{T}\) and in \(\mathcal{D}\), as follows:

• If \(\mathcal{T}(u)\) is a common ancestor, then \(\mathsf{Near}(u,s)\) contains both \(x\) and \(y\), and hence \(e\) cannot contribute to any \(u,s\)-mincut. Namely, common ancestors in \(\mathcal{T}\) cannot contain vertices that separate \(x,y\).

• If \(\mathcal{D}(u)\) is a non-ancestor, then \(\mathsf{Far}(u,s)\) keeps both \(x\) and \(y\) outside, and hence \(e\) cannot contribute to any \(u,s\)-mincut. Namely, non-ancestors in \(\mathcal{D}\) cannot contain vertices that separate \(x,y\).

To conclude, each of \(\mathcal{T}\) and \(\mathcal{D}\) has one non-trivial type: in \(\mathcal{T}\) these are the non-ancestors, while in \(\mathcal{D}\) these are the common ancestors. Intuitively, this is what makes \(\mathcal{D}\) preferable: its non-trivial nodes are well-structured. Indeed, if \(\mathcal{D}\) were a tree, the common ancestors would form a path from the root to the LCA (lowest/least common ancestor), so any two of them would be related by ancestry. It turns out that even though \(\mathcal{D}\) is a DAG, it still admits a very similar property: among any three common ancestors, at least two are related by ancestry. This is by the following lemma:

In particular, this lemma implies that \(\mathcal{D}(x)\) and \(\mathcal{D}(y)\) can have at most two LCAs in \(\mathcal{D}\).¹¹ 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:

1. Given \(e = \{x,y\} \in E\) and LCA \(\mu\) of \(\mathcal{D}(x),\mathcal{D}(y)\), report all vertices \(u \in \mathcal{D}^{\uparrow}(\mu)\) that separate \(x,y\).

3.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 \(\mathcal{D}\). Consider an arbitrary \((u,s)\)-mincut \(U\). Then of course, \(U \subseteq \mathsf{Far}(u,s) = \mathcal{D}_{\downarrow}(u)\), i.e., \(U\) only contains vertices from descendants of \(\mathcal{D}(u)\). Other than that, \(U\) need not “respect” the structure of \(\mathcal{D}\): for a descendant node \(\mu\) of \(\mathcal{D}(u)\), it could be that \(U\) keeps \(\mu\) entirely inside, entirely outside, or—“worst of all”—it could even splits \(\mu\) between its sides, which indeed turns out most challenging for us. Our key insight to mitigate this challenge is that if \(\mu\) is split by \(U\), then the partition \(\mu \cap U, \mu \cap \overline{U}\) cannot be arbitrary: it must be a valid partition of \(\mu\) (see 2.1). This is because \(U\) “induces” a \(\mu\)-mincut, as formalized in the following simple-yet-crucial lemma:

Thus, 4 provides a “bridge” between single-source mincuts and Steiner mincuts: It serves as a key that unlocks the powers of the connectivity carcass, and allows us to harness them for our purposes.

3.3 Utilizing Skeletons for \(O(m)\) Space and \(O(n)\) Query Time↩︎

As detailed in 2, the connectivity carcass has several components; the simplest and most well-known is the skeleton, a cactus representation for all valid partitions of the terminals (see 4). It turns out that by only utilizing skeletons, together with our previous insights on \(\mathcal{D}\), we can already provide a non-trivial data structure for Query [query-Q] with \(O(m)\) space and \(O(n)\) query time, through a tool we term the representatives framework.

On a high-level, the representative framework provides a succinct characterization for the set of vertices \(u\) that separate two vertices \(x,y\), which is precisely what we need for Query [query-Q]. The framework even applies more generally, if we replace the two vertices \(x,y\) with two non-empty subsets of vertices \(P,Q\). This generalization would be critical for us to obtain an optimal \(O(n)\) space bound, as will be explained later on in this overview. The framework associates \(O(1)\) representative information \(\mathrm{\small rep}(P,Q)\) with any such pair \(P,Q\). This information, along with the \(O(n)\) global information consisting of the DAG \(\mathcal{D}\) and the skeletons \(\mathcal{H}_\nu\) associated with each node \(\nu\) of \(\mathcal{D}\), essentially encodes all the vertices \(u\) that separate \(P,Q\) (namely, such that some \(u,s\)-mincut keeps \(P\) and \(Q\) on different sides). The following lemma provides the interface of this framework.

Given 5, we immediately get an \(O(m)\) space data structure that answers Query [query-Q] within \(O(n)\) time: we just store \(\mathrm{\small rep}(x,y)\) for every edge \(e = \{x,y\} \in E\) and the \(O(n)\) space global structure from 5. We now outline what is going on behind the hood of 5, and explain the essential role of skeletons in obtaining it.

• First, by exploiting 3, we show that there exists \(O(1)\) representative nodes \(\nu_1, \nu_2, \dots\) for \(P,Q\), such that every \(u\) which separates \(P,Q\) must lie in a descendant node of some \(\nu_i\). Conversely, by using sub/posimodularity and the structure of \(\mathcal{D}\), we prove that if vertex \(u\) lies in a strict descendant of some \(\nu_i\) and satisfies \(P \cup Q \subseteq \mathcal{D}_{\downarrow}(u)\), then \(u\) must separate \(P,Q\). We let \(\mathrm{\small rep}(P,Q)\) store the names of \(\nu_1, \nu_2, \dots\). So, using this information and the “global” DAG \(\mathcal{D}\), we can classify every vertex \(u \in \mathcal{D}^{\uparrow}(\mu)\) as separating \(P,Q\) or not, except for those vertices inside the representative nodes.

• Let us now zoom-in on one representative node \(\nu_i\). By a structural analysis based on sub/posimodularity, we show that there exists \(O(1)\) mincuts-to-\(s\) \(U_1, U_2, \dots\) such that those vertices of \(\nu_i\) that separate \(P,Q\) are precisely \(\nu_i \cap (U_1 \cup U_2 \cup \cdots)\). By the “bridge” 4, each \(\nu_i \cap U_j\) defines a valid partition of \(\nu_i\), and thus can be determined as the terminals in one side of a corresponding canonical cut \(C_{ij}\) in the skeleton \(\mathcal{H}_{\nu_i}\). Crucially, such a canonical cut \(C_{ij}\) with a “marked” side can be compactly represented by storing the one or two skeleton edges of \(C_{ij}\), with marking on their endpoints from the marked side. So, we let \(\mathrm{\small rep}(P,Q)\) store \(C_{i1},C_{i2},\dots\) (with the markings), and together with the “global” skeleton \(\mathcal{H}_{\nu_i}\), this lets us determine which vertices in \(\nu_i\) that separate \(P,Q\).

To keep the overview focused, from now on we will only care about the space of our data structure for Query [query-Q], and neglect query time; the latter can be made \(O(n)\) by using some technical extensions of the representative framework.

3.4 Utilizing Projections Towards \(O(n)\) Space↩︎

Up until now, we have only used the skeleton component of the carcass, which enabled us to get down to \(O(m)\) space. To get optimal \(O(n)\) space, we need to use the more complicated and crucial component of the carcass: the projection mapping (see 5 and 6).

3.4.0.1 Warm-Up: Internal Edges.

As a warm-up to demonstrate our use of projections, we first discuss a special case of Query [query-Q]: the query edge \(e = \{x,y\}\) is internal, i.e., \(x\) and \(y\) are from the same node \(\mu\) of \(\mathcal{D}\), which is trivially the unique LCA of \(\mathcal{D}(x),\mathcal{D}(y)\). The main insight for this special case is the following. Consider any vertex \(u \in \mathcal{D}^{\uparrow}(\mu)\) which we should classify as separating \(x,y\) or not. Let \(U\) be some arbitrary \((u,s)\)-mincut. Using our “bridge to the carcass”, we can characterize precisely when \(U\) separates \(x,y\) in terms of the projection \(\pi_\mu (e)\), which is a proper path in the skeleton \(\mathcal{H}_\mu\).

To utilize this insight through the representative framework, we show a rather simple property of the skeleton: Each skeleton edge \(g\) in \(\mathcal{H}_\mu\) has two sets of associated terminals \(\mu_0 (g), \mu_1 (g) \subseteq \mu\), such that the canonical cuts containing \(g\) correspond exactly to the valid partitions keeping \(\mu_0 (g)\) and \(\mu_1 (g)\) on different parts. We say that \(u\) separates \(g\) if it separates \(\mu_0 (g), \mu_1 (g)\) (i.e., some \(u,s\)-mincut keeps these sets on different sides), and define \(\mathrm{\small rep}(g) = \mathrm{\small rep}(\mu_0 (g), \mu_1 (g))\). Thus, by the previous claim, we obtain that

In light of this discussion, our \(O(n)\) space data structure for “internal” Query [query-Q] consists of:

• The \(O(n)\) space global structure of the representatives framework from 5.

• For each node \(\mu\) in \(\mathcal{D}\), the skeleton \(\mathcal{H}_\mu\) is stored along with \(\mathrm{\small rep}(g)\) for each skeleton edge \(g\) of \(\mathcal{H}_\mu\).

As \(\mathcal{H}_\mu\) has \(O(|\mu|)\) edges, and \(\mathrm{\small rep}(g)\) takes up \(O(1)\) space, this amounts only to \(O(n)\) storage overall. Now, to answer a query of \(e = \{x,y\} \in E\) with \(x,y \in \mu\), we find the unique proper path between the nodes \(\pi_\mu (x)\) and \(\pi_\mu (y)\) in the skeleton \(\mathcal{H}_\mu\), which is \(\pi_\mu (e)\) by 6. Then, for each edge \(g\) of \(\pi_\mu (e)\), we use \(\mathrm{\small rep}(g)\) in 5 to find all vertices \(\mathcal{D}^{\uparrow}(\mu)\) that separate \(g\), and return the union of all found vertices, which is all those \(u \in \mathcal{D}^{\uparrow}(\mu)\) that separate \(x,y\) by 8.

3.4.0.2 The General Case.

From now on, we discuss the strategy for generalizing the internal case and handling Query [query-Q] with any edge \(e = \{x,y\}\). Unlike the internal case, now we need to consider two types of mincuts to \(s\) which separate \(x,y\): 1) those that split \(\mu\), and 2) those placing all of \(\mu\) entirely on one side (the latter were impossible when \(x,y \in \mu\)). We thus fork query [query-Q] into two queries:

Given \(e = \{x,y\} \in E\) and an LCA \(\mu\) of \(\mathcal{D}(x),\mathcal{D}(y)\),

1. report all \(u \in \mathcal{D}^{\uparrow}(\mu)\) such that some \(u,s\)-mincut separates \(x,y\) and splits \(\mu\).

2. report all \(u \in \mathcal{D}^{\uparrow}(\mu)\) such that some \(u,s\)-mincut separates \(x,y\) and keeps \(\mu\) on one side.

Query [query-Q1] turns out to be the more challenging one, so we focus only on it in this overview.

3.4.0.3 Anchors and Query Translation.

As in the internal case, the projection path \(\pi_\mu(e)\) in the skeleton \(\mathcal{H}_\mu\) will still play a crucial role for us, though its use will be more involved. But, before we can use \(\pi_\mu (e)\), we are first faced with a more basic challenge: how can we even find \(\pi_\mu (e)\)? Recall that \(\pi_\mu (e)\) is the unique proper path that has \(\pi_\mu (x)\) and \(\pi_\mu (y)\) as a prefix and suffix. When \(e\) was internal, \(x,y\) were terminals, so their projections are given directly from the skeleton \(\mathcal{H}_\mu\), which we store. But in general, \(x\) and/or \(y\) are non-terminals, and so we do not have the budget to explicitly store their projections in \(\mathcal{H}_\mu\). Our strategy to tackle this challenge goes through the notion of anchors, introduced in the following definition:

Relying on sub/posimodularity and the properties of the farthest mincut DAG \(\mathcal{D}\), we are able to prove that the anchors \(z_x\) and \(z_y\) are “equivalent” to the endpoints of the query edge \(e = \{x,y\}\), in every meaningful sense for us. So, our strategy is to “translate” the original query endpoints \(x,y\) to their anchors \(z_x, z_y\). In particular, it turns out that \(\pi_\mu (z_x)\) and \(\pi_\mu (z_y)\) form a prefix and suffix of the proper path \(\pi_\mu(e)\), in a similar fashion to \(\pi_\mu (x)\) and \(\pi_\mu (y)\) (although \(\pi_\mu (z_x)\) might not be equal to \(\pi_\mu (x)\), and similarly with \(z_y\) and \(y\)). Thus, we can store the projections \(\pi_\mu (z_\nu)\) for each edge \((\mu, \nu)\) of \(\mathcal{D}\), and still be able to recover the projection path \(\pi_\mu (e)\) at query time as desired; this only requires \(O(n)\) space since \(\mathcal{D}\) has \(O(n)\) edges.

As mentioned before, finding \(\pi_\mu (e)\) is merely one basic challenge that we need to overcome. However, the equivalence of the anchors \(z_x,z_y\) to the endpoints \(x,y\) is key to reducing the space needed to tackle other challenges as well: in essence, whenever we would like to store some \(O(1)\) information for a vertex as a “potential endpoint” of the yet-unknown query edge whose LCA is \(\mu\), we can just store it for the anchor instead, and this will result in \(O(n)\) storage overall. So, exploiting this equivalence, in the remaining discussion we simply assume that \(x = z_x\) and \(y = z_y\).

3.4.0.4 Generalizing the Structural Analysis.

Finally, we give an overview of the more complicated structural insights to treat the general case of Query [query-Q1], which play an analogous role to 8 for the internal case. One direction of 8 remains true: if \(u\) separates \(x,y\) (by a cut that splits \(\mu\)), then \(u\) must separate some edge \(g\) of \(\pi_\mu (e)\). However, the converse direction is no longer true. This is because now \(x\) or \(y\) might be stretched vertices. We illustrate the issue through a hypothetical example:

• Say \(\pi_\mu (x)\) is a prefix of \(\pi_\mu (e)\) with at least one edge \(g\), which is a tree-edge; then \(\mu_0 (g), \mu_1 (g)\) form the valid partition corresponding to \(g\), which distinguishes \(x\) by 5. So, there are \((\mu_0 (g),\mu_1 (g))\)-mincuts \(A\) and \(B\) s.t.\(x \in A\) and \(x \notin B\); say \(A,B\) are the only \((\mu_0 (g) ,\mu_1 (g))\)-mincuts.

• Say there is a unique \((u,s)\)-mincut \(U\) splitting \(\mu\), where \(\mu_0 (g) \subseteq U\), \(\mu_1 (g) \subseteq \overline{U}\). Thus, \(u\) separates \(g\).

• Finally, say \(y \in \overline{U}\). Thus, \(u\) should be included in the output for Query [query-Q1] iff \(x \in U\). By 4, \(W := U \cap \mathcal{D}_{\downarrow}(\mu)\) is a \((\mu_0 (g),\mu_1 (g))\)-mincut. Note that \(x \in U\) iff \(x \in W\). However, we have no way of telling if \(W\) is equal to \(A\) or to \(B\), and accordingly, both \(x \in U\) and \(x \notin U\) are possible.

So, we need new tools to help us characterize precisely those “false positive” cases where \(u\) separates \(\pi_\mu (e)\) but does not separate \(x,y\). These come from storing some additional information with the vertex projections \(\pi_\mu (x)\) and \(\pi_\mu (y)\), as follows.

First, we show that one can associate two terminal sets \(\mu_0 (x)\) and \(\mu_1 (x)\) with the proper path \(\pi_\mu (x)\), in a similar fashion to what we did with single skeleton edges: the canonical cuts having an edge from \(\pi_\mu (x)\) correspond precisely to the valid partitions keeping \(\mu_0 (x)\) and \(\mu_1 (x)\) on different parts. Further, each of the sets \(\mu_0 (x), \mu_1 (x)\) has a “matching endpoint” of \(\pi_\mu (x)\): the endpoint which matches \(\mu_i (x)\) lies in the same side as \(\mu_i (x)\) of any canonical cut that splits \(\mu_0 (x)\) and \(\mu_1 (x)\). We store the representative information \(\mathrm{\small rep}(\mu_0 (x) \cup \{x\}, \mu_1 (x))\) and \(\mathrm{\small rep}(\mu_0(x), \mu_1 (x) \cup \{x\})\). This is done during preprocessing, hence we also store symmetric information also for \(\pi_\mu (y)\).

At query time, using some additional technical tools, we determine which of \(\mu_0 (x)\) or \(\mu_1 (x)\) matches the \(x\)-endpoint of \(\pi_\mu (e)\); say \(\mu_0 (x)\). Then, define \(A_\mu (x)\) as the set of all vertices from \(\mathcal{D}^{\uparrow}(\mu)\) that have some mincut to \(s\) which keeps \(x\) with \(\mu_0 (x)\) on one side, and \(\mu_1 (x)\) on the other. This set can be found by using \(\mathrm{\small rep}(\mu_0 (x) \cup \{x\}, \mu_1 (x))\) in the representative framework (5). We define \(A_\mu (y)\) and find it in a symmetric fashion. Next, similarly as in the internal case, we find \(\pi_\mu (e)\) as the unique proper path in \(\mathcal{H}_\mu\) that starts with \(\pi_\mu (x)\) and ends with \(\pi_\mu(y)\) (by 6), and for each edge \(g\) in \(\pi_\mu (e)\), we use \(\mathrm{\small rep}(g)\) in the representatives framework to find the set of all vertices from \(\mathcal{D}^{\uparrow}(\mu)\) that separate \(g\).

The analog of 8 from the internal case is the following characterization, showing that the information we have obtained can be used to exactly find those vertices \(u \in \mathcal{D}^{\uparrow}(\mu)\) that have some \(u,s\)-mincut which separates \(x,y\) and splits \(\mu\), which should be reported for Query [query-Q1].

• If \(u\) separates a “middle” edge from \(\pi_\mu (e) \setminus (\pi_\mu (x) \cup \pi_\mu (y))\): Report \(u\).

• Else, if \(u\) separates an “overlap” edge from \(\pi_\mu (x) \cap \pi_\mu (y)\): Report \(u\) iff \(u \in A_\mu (x) \cap A_\mu (y)\).

• Else, if \(u\) separates a “wing” edge from \(\pi_\mu (e) \setminus (\pi_\mu (x) \cap \pi_\mu (y))\): Report \(u\) iff \(u \in A_\mu (x) \cup A_\mu (y)\).

• Else, when \(u\) does not separate any edge from \(\pi_\mu (e)\): Do not report \(u\).

The correctness proof of the above characterization is based on delicate structural arguments, relying on sub/posimodularity and carcass properties (using the bridge 4).

3.5 Organization↩︎

The rest of the paper is organized as follows.

• We start by introducing the tools required for our oracles. 4 gives some new carcass tools needed for our results, which essentially add some capabilities to its basic interface from 2.1 (the proofs for this section appear in 12). The next 5 gives the details of the representatives framework discussed in 3.3. The following 6 gives the formal “query translation” using the anchors discussed in 3.4.0.3.

• After all the needed tools are given, we provide the data structures for Query [query-Q1] and Query [query-Q2] in [sec:splitting-mu] and 8 respectively, which together give the proof of our main 1.

• 9 then introduces our data structure for queries on the farthest mincut DAG, and combines it with the previous tools to the fast-query oracles of 2 and 3. The insertion variant of 2 appears in 14.

• Some straightforward lower bounds are given in 13: (1) \(\Omega(n)\) space is needed even for the fixed-pair setting, and (2) the directed single-source setting needs \(\Omega(n^2)\) space.

4 Carcass Tools↩︎

This section introduces several new tools regarding the connectivity carcass, which was presented in the Preliminaries (2.1). These are used in a black-box manner by our data structures; we therefore provide only their interfaces here, with the proofs deferred to 12. As in 2.1, the terminal set is denoted by \(S\).

4.0.0.1 Associated Terminals.

As mentioned in [sec:internal-overview,sec:general-case-overview], we use a mechanism of associated terminal sets for skeleton edges and proper paths. These are defined as follows:

We have the following property of associated terminal sets on proper paths:

The main point of 3 is to ensure the correctness of the following 7. The somewhat tedious proof is based on the skeleton properties of 4, the main one being the bijection between canonical cuts and valid partitions.

4.0.0.2 Translation Lemma.

Our next tool concerns the process of query translation to the anchors, overviewed in 3.4.0.2. Specifically, it is used to prove that the projections of the anchors \(z_x\) and \(z_y\) form a prefix and suffix of the projection of \(e = \{x,y\}\) in 1. (Here, \(x',y'\) play the roles of \(z_x,z_y\).)

4.0.0.3 Skeleton Tools.

We now present some tools pertaining to the skeleton \(\mathcal{H}_S\). The first is an algorithm for computing the union of (marked sides) of canonical cuts, which will be useful for a generalization of the representatives framework (13) that allows us to achieve the (worst-case optimal) \(O(n)\) query time in 1.

Next, we present some data structures for the skeleton. These are not required for our main 1, but needed for the data structures of 2 that support faster queries.

4.0.0.4 Numbering for Projection Directionality.

The following 12 is a technical lemma that assigns numbers to vertices, helping us deal with certain “directionality properties” of projections in certain corner cases. We use it in [sec:splitting-mu]. Specifically, our use-case is (roughly) as follows: if edge \(e = \{x,y\}\) has its projection \(\pi_S (e)\) equal to both \(\pi_S (x)\) and \(\pi_S (y)\), we can use the numbers assigned to \(x\) and \(y\) in order to determine the \(x\)-endpoint and the \(y\)-endpoint of \(\pi_S (e)\). This lemma is not new: it has appeared before in [4], [9], but was stated using carcass terminologies which we bypass in this paper. Thus, we give an explicit statement and provide a proof that assumes only the carcass preliminaries of 2.1.

5 The Representatives Framework↩︎

In this section, we give the details of the representative framework, which was overviewed in 3.3. The framework associates \(O(1)\) representative information with any unordered pair \(P,Q\) of non-empty vertex subsets, in such a manner that guarantees the following (which is generalized version of 5):

Recall that vertex \(u\) is said to separate \(P,Q\) if there exists a \(u,s\)-mincut which keeps \(P\) on one side and \(Q\) on the other. We will also need an ordered version of this terminology: we say that \(u\) separates \((P,Q)\) if there exists a \((u,s)\)-minuct \(U\) such that \(P \subseteq U\) and \(Q \subseteq \overline{U}\). Thus, \(u\) separates \(P,Q\) iff \(u\) separates \((P,Q)\) or \(u\) separates \((Q,P)\).

5.0.0.1 Representative Nodes.

In order to prove 13, we first need to define \(\mathrm{\small rep}(P,Q)\). In fact, each ordered pair \((P,Q)\) or \((Q,P)\) has its own representative information, and \(\mathrm{\small rep}(P,Q)\) consists of the information for both; we arbitrarily focus on \((P,Q)\). The first ingredient is the representative nodes, defined in the following lemma.

One may hope for the following “converse to 14”: if \(\mathcal{D}(u)\) has some representative node for \((P,Q)\) as an ancestor, then \(u\) should separate \((P,Q)\). While this fails, we next prove an “almost-converse”; the caveats are in conditions (ii) and (iii), and in the conclusion of separating the unordered \(P,Q\).

5.0.0.2 Representative Cuts.

Let us now focus on characterizing which vertices inside the representative nodes separate \((P,Q)\); these are not treated by 15 because of condition (ii). While a representative node \(\nu\) must contain some vertex separating \((P,Q)\), it may also contain vertices that do not separate \((P,Q)\), or even that do not separate \(P,Q\). The second ingredient of the representative information consists of canonical cuts of the skeleton \(\mathcal{H}_\nu\), that precisely characterize which vertices inside \(\nu\) separate \((P,Q)\). These are called the representative cuts, defined in the following lemma:

Crucially, each (non-degenerate) representative cut is a canonical cut in its skeleton, which is represented just by its one or two skeleton edges with markings on their endpoints from the marked side (for example, the cut defined by two purple cycle-edges in the Skeleton in 1).

5.0.0.3 Putting It All Together.

We can now finally define \(\mathrm{\small rep}(P,Q)\) and prove 13.

6 Anchors and Query Translation↩︎

In this section, we formally prove the useful properties of the anchors used for the query translation process, overviewed in 3.4.0.3. We first restate the definition of pivots and anchors:

The following lemma formalizes the essential equivalence between the endpoints \(x,y\) of the failing edge, and their anchors \(z_x, z_y\) with respect to an LCA \(\mu\) of \(\mathcal{D}(x),\mathcal{D}(y)\).

Finally, as explained in 3.4.0.3, the projections of the anchors in the skeleton of the LCA \(\mu\) play a crucial role, as they enable us to find the projection of the edge \(e\). This is obtained by 1, which is derived from the equivalence of anchors in 17 and our carcass translation lemma (8); see 3.

7 Mincuts Splitting the LCA↩︎

This section provides the data structure for Query [query-Q1], restated below; See the overview in 3.4.0.2.

1. Given \(e = \{x,y\} \in E\) and an LCA \(\mu\) of \(\mathcal{D}(x),\mathcal{D}(y)\), report all \(u \in \mathcal{D}^{\uparrow}(\mu)\) such that some \(u,s\)-mincut separates \(x,y\) and splits \(\mu\).

Note that by the equivalence of \(x,y\) to their anchors \(z_x,z_y\) w.r.t.\(\mu\) from 17, the condition in Query [query-Q1] is equivalent to “some \(u,s\)-mincut separates \(z_x,z_y\) and splits \(\mu\)”; this new condition would be the one that we will use. Our goal in this section is to show:

Our first step is to formally define the \(A_\mu (\cdot)\) sets, which are crucial to our query algorithm, as mentioned in the overview (3.4.0.2).

7.1 Construction↩︎

We now formally describe the information stored by our data structure for Query [query-Q1].

First, we store the \(O(n)\) global data structure for the representative framework of 13, which consists of the DAG \(\mathcal{D}\) and the skeletons \(\mathcal{H}_\mu\) for each node \(\mu\) of \(\mathcal{D}\). We augment each skeleton edge \(g = \{a,b\}\) in \(\mathcal{H}_\mu\) with its \(O(1)\) representative information \(\mathrm{\small rep}(g) := \mathrm{\small rep}(\mu(a,g),\mu(b,g))\) (see 3 for the definition of \(\mu(a,g)\), and \(\mu(b,g)\)).

Next, for each node \(\mu\) in \(\mathcal{D}(\mu)\), we store the values \(\lambda_\mu\) and \(c(\mathcal{D}_{\downarrow}(\mu))\), and the following \(O(1)\) information for every \(z \in \{z_\nu \mid \text{\nu child of \mu}\} \cup \mu\), consumes a total of \(O(|\mu| + \operatorname{outdeg}_\mathcal{D}(\mu))\) space for \(\mu\):

• The \(\mu\)-equivalence class number \(\phi_\mu (z)\), and the \(\sigma_\mu (z)\) number of 12.

• The endpoints \(a_0 (z)\) and \(a_1 (z)\) of the projection \(\pi_\mu (z)\) (see 5). Note that these endpoints are distinct if \(z\) is stretched, and equal otherwise.

• The representative information for \(A_\mu^{(0)}(z)\) and to \(A_\mu^{(1)}(z)\), namely \(\mathrm{\small rep}(\mu_0(z) \cup \{z\}, \mu_1 (z))\) and \(\mathrm{\small rep}(\mu_0(z), \mu_1(z) \cup \{z\})\). These are defined only if \(z\) is stretched (see 5).

As the nodes of \(\mathcal{D}\) partition the vertices in \(V\), and because \(\sum_\mu \operatorname{outdeg}_\mathcal{D}(\mu)\) counts each of the \(O(n)\) edges of \(\mathcal{D}\) exactly once, the total space occupied by the data structure is \(O(n)\).

7.2 Query Algorithm↩︎

We now give the algorithm to answer Query [query-Q1], given edge \(e = \{x,y\} \in E\) and LCA \(\mu\) of \(\mathcal{D}(x),\mathcal{D}(y)\).

Step 0:

Find the anchors \(z_x,z_y\) of \(x,y\) w.r.t.\(\mu\), which takes \(O(n)\) time by searching \(\mathcal{D}\). Note that by their definition ([def:32anchors]), \(z_x,z_y \in \{z_\nu \mid \text{\nu child of \mu}\} \cup \mu\) .

Step 1:

If \(\lambda_\mu \neq c(\mathcal{D}_{\downarrow}(\mu))\) or \(\phi_\mu (z_x) = \phi_\mu (z_y)\): Halt without reporting any vertex.

Step 2:

Use the stored endpoints of \(\pi_\mu (z_x)\) and \(\pi_\mu (z_y)\) as the unique proper paths between their endpoints (or, if \(z_x\) and/or \(z_y\) are non-stretched, the projections are nodes) in \(\mathcal{H}_\mu\). Next, compute \(\pi_\mu (e)\) as the unique proper path that starts with \(\pi_\mu (z_x)\) and ends with \(\pi_\mu (z_y)\); this path indeed exists and is equal to \(\pi_\mu (e)\) by 1, since we did not halt in Step 1. These computations on \(\mathcal{H}_\mu\) take \(O(|\mu|) \leq O(n)\) time, and let us to determine the edges in each of the following subpaths of \(\pi_\mu (e)\) (see 4):

1. middle part \(\pi_\mu (e) \setminus (\pi_\mu (z_x) \cup \pi_\mu (z_y))\),

2. overlap \(\pi_\mu (z_x) \cap \pi_\mu (z_y)\),

3. prefix \(\pi_\mu (z_x) \setminus \pi_\mu (z_y)\),

4. suffix \(\pi_\mu (z_y) \setminus \pi_\mu (z_x)\).

For each \(P\) among (i)-(iv), find the set \(\{ u \in \mathcal{D}^{\uparrow}(\mu) \mid \text{u separates some edge g of P}\}\) by applying the representative framework from 13 with \(\{\mathrm{\small rep}(g)\}_{g \in P}\). As \(P\) has at most \(O(|\mu|) \leq O(n)\) edges, this takes \(O(n)\) time by 13.

Step 3:

Determine the \(x\)-endpoint \(a_x\) and the \(y\)-endpoint \(a_y\) of \(\pi_\mu (e)\), and hence also the edges \(g_x\) and \(g_y\) of \(\pi_\mu(e)\) adjacent to \(a_x\) and to \(a_y\) respectively (where possibly \(g_x = g_y\)), as follows.

• If \(\pi_\mu (z_x) \neq \pi_\mu (y)\), then either the \(x\)-endpoint lies uniquely on the prefix (iii), or the \(y\)-endpoint lies uniquely on the suffix (iv), so we are done.

• If \(\pi_\mu (z_x) = \pi_\mu (y)\), then compare \(\sigma_\mu (z_x)\) and \(\sigma_\mu (z_y)\). If \(\sigma_\mu (z_x) < \sigma_\mu (z_y)\), then the \(x\)-endpoint of \(\pi_\mu (e)\) is the one with smaller identifier; otherwise it is the one with larger identifier. The correctness of this step is proved in 20.

If \(z_x\) is stretched, let \(i \in \{0,1\}\) be such that \(a_x = a_i (z_x)\), and use \(\mathrm{\small rep}(\mu_i (z_x) \cup \{x\}, \mu_{1-i} (z_x))\) with the representative framework of 13 to compute \(A_\mu (z_x) := A_\mu^{(i)} (z_x)\) within \(O(n)\) time. If \(z_x\) is non-stretched, let \(A_\mu (z_x) := \emptyset\). Similarly, if \(z_y\) is stretched, let \(j \in \{0,1\}\) be such that \(a_y = a_j (z_y)\), and compute \(A_\mu (z_y) := A_\mu^{(j)}(z_y)\) is a similar fashion, and if \(z_y\) is non-stretched then \(A_\mu (z_y) := \emptyset\). This takes \(O(n)\) time by 13.

Step 4:

Find all vertices \(u \in \mathcal{D}^{\uparrow}(\mu)\) within \(O(n)\) time by searching \(\mathcal{D}\). Then, for each \(u \in \mathcal{D}^{\uparrow}(\mu)\), decide within \(O(1)\) time whether to report \(u\) as part of the output for Query [query-Q1] as follows:

1. If \(u\) separates an edge of the middle part (i): Report \(u\).

2. Else, if \(u\) separates an edge of the overlap (ii): Report \(u\) iff \(u \in A_\mu (z_x) \cap A_\mu (z_y)\).

3. Else, if \(u\) separates an edge of the prefix (iii) or the suffix (iv): Report \(u\) iff \(u \in A_\mu (z_x) \cup A_\mu (z_y)\).

4. Else: Do not report \(u\).

Thus, our data structure answers Query [query-Q1] within \(O(n)\) time.

7.3 Correctness↩︎

We first need to prove that Step 1 is correct:

So, for the rest of the correctness proof (i.e., in all of the following lemmas), we will implicitly assume that the query algorithm did not stop in Step 1, i.e., that \(\lambda_\mu = c(\mathcal{D}_{\downarrow}(\mu))\) and \(\phi_\mu (z_x) \neq \phi_\mu (z_y)\). Thus, 1 is assumed to apply: \(\pi_\mu(e)\) is defined, and has \(\pi_\mu (z_x)\) as a prefix and \(\pi_\mu (z_y)\) as a suffix in the direction from the \(x\)-endpoint \(a_x\) to its \(y\)-endpoint \(a_y\). Next, we need to prove that Step 3 correctly identifies the \(x\)-endpoint and the \(y\)-endpoint. This is clear in case \(\pi_\mu (z_x) \neq \pi_\mu (z_y)\). For the other case, this is due to the properties of the \(\sigma_\mu (\cdot)\) numbers from 12:

We now arrive at the main part of the correctness analysis: proving that Step 4 is correct. From now on, we fix \(u \in \mathcal{D}^{\uparrow}(\mu)\), and our goal is to show that our query algorithm determines whether to report \(u\), namely, \(u\) is reported precisely when there exists a \(u,s\)-mincut which separates \(z_x,z_y\) and splits \(\mu\).

Before treating each substep separately, we show a “helper lemma”, useful for several of them.

Our proofs also repeatedly use the following observations, which follow immediately from 6 and the definitions of \(\mu_i (z_x), \mu_{1-i}(z_x), \mu_j (z_y), \mu_{1-j}(z_y)\).

Finally, the following four lemmas correspond to the correctness of each of the four substeps 4a-4b.

This concludes the proof of 18.

8 Mincuts Not Splitting the LCA↩︎

This section provides the data structure for Query [query-Q2], restated below.

1. Given \(e = \{x,y\} \in E\) and an LCA \(\mu\) of \(\mathcal{D}(x),\mathcal{D}(y)\), report all \(u \in \mathcal{D}^{\uparrow}(\mu)\) such that some \(u,s\)-mincut separates \(x,y\) and keeps \(\mu\) on one side.

Again, as was with Query [query-Q1], by 17 the condition in Query [query-Q2] is equivalent to “some \(u,s\)-mincut separates \(z_x,z_y\) and keeps \(\mu\) on one side”, where \(z_x,z_y\) are the anchors of \(x,y\) w.r.t.\(\mu\). So, our goal in this section is to show:

We will need the following tool, which is similar to 12.

8.1 Construction↩︎

We now formally describe the information stored by our data structure for Query [query-Q2]. First, we store the \(O(n)\) space data structure of the representative framework from 13. Next, for each node \(\mu\) of \(\mathcal{D}\), and each \(z \in \{z_\nu \mid \text{\nu child of \mu}\} \cup \mu\), we store \(\mathrm{\small rep}(\mu, z)\), and the number \(\tau_\mu (z)\) from 27, which consumes a total of \(O(|\mu| + \operatorname{outdeg}_\mathcal{D}(\mu))\) space for \(\mu\). Because the nodes of \(\mathcal{D}\) partition the vertices \(V\), and because \(\sum_\mu \operatorname{outdeg}_\mathcal{D}(\mu)\) counts each of the \(O(n)\) edges of \(\mathcal{D}\) exactly once, the total space is \(O(n)\).

8.2 Query Algorithm↩︎

We now give the algorithm to answer Query [query-Q2], given \(e = \{x,y\} \in E\) and LCA \(\mu\) of \(\mathcal{D}(x),\mathcal{D}(y)\).

Step 0:

Find the anchors \(z_x,z_y\) of \(x,y\) w.r.t.\(\mu\), which takes \(O(n)\) time by searching \(\mathcal{D}\). Note thta \(z_x,z_y \in \{z_\nu \mid \text{\nu child of \mu}\}\) by [def:32anchors].

Step 1:

Use \(\mathrm{\small rep}(\mu, z_x)\) in 13 to determine the set \(B(z_x) = \{u \in \mathcal{D}^{\uparrow}(\mu) \mid \text{u separates \mu,z_x}\}\). Similarly, use \(\mathrm{\small rep}(\mu,z_y)\) to compute \(B(z_y) = \{u \in \mathcal{D}^{\uparrow}(\mu) \mid \text{u separates \mu,z_y}\}\). This takes \(O(n)\) time by 13.

Step 2:

Answer the query as follows.

1. If \(\tau_\mu (z_x) = \tau_\mu (z_y)\): Return \(\emptyset\).

2. If \(\tau_\mu (z_x) < \tau_\mu (z_y)\): Return \(B(z_y)\).

3. If \(\tau_\mu (z_x) > \tau_\mu (z_y)\): Return \(B(z_x)\).

Thus, our data structure answers Query [query-Q2] within \(O(n)\) time.

8.3 Correctness↩︎

First, we prove the following “helper” lemma:

We now prove the correctness of the substeps of Step 2. As 2b and 2c are completely symmetric, we only consider 2b here. For this, we fix any \(u \in \mathcal{D}^{\uparrow}(\mu)\), and show that \(u\) is reported in the output of our algorithm precisely when there is some \(u,s\)-mincut which separates \(z_x,z_y\) and keeps \(\mu\) on one side.

This concludes the proof of 26.

9 Data Structures for Fast Queries: Output-Sensitive and One-Destination↩︎

In this section, we show how, by allowing space of \(O(n^{1.5})\), we can support faster edge-failure queries for single-source mincuts as stated in 2: an output-sensitive query algorithm that reports all vertices whose mincut to \(s\) in time which is proportional to their number up to an \(\log^3 n\) factor, and a one-destination query algorithm that, given a single destination vertex of interest as part of the query, determines whether its mincut to \(s\) changes upon the failure in \(O(\log n)\) time.

9.1 Ancestry and LCA in Farthest Mincut DAG↩︎

The most important component of 2 is a data structure for the farthest mincut \(\mathcal{D}\) that occupies \(O(n^{1.5})\) and supports fast ancestry and LCA queries, which is given in 31 below. In fact, this is the only component of our data structure with \(O(n^{1.5})\) space, where all other components only need \(O(n \log n)\) space. Improving the space of this ancestry/LCA structure beyond \(O(n^{1.5})\) while maintaining polylogarithmic query time would directly yield an improved space bound for the entire data structure, and doing so appears to be a challenging and interesting problem.

We mention that the \(O(n^{1.5})\) space bound is by itself non-trivial, and might seem surprising in light of the Reachability Conjecture [15], [16]. This conjecture states that any data structure supporting reachability (i.e., ancestry) queries for DAGs with \(n\) vertices and \(m\) edges must either spend \(\tilde{\Omega}(m)\) query time or consume \(\tilde{O}(n^2)\) space in the worst case. However, the farthest mincut DAG \(\mathcal{D}\) is not worst-case; it is very well-structured due to 3, which is the key to obtaining the data structure.

9.2 Extensions of The Representatives Framework↩︎

We now present two extensions of the representative framework using the ancestry data structure for \(\mathcal{D}\) of 31. The first extension is useful for the One-Destinations queries:

The second extension is useful for the output-sensitive query algorithm, and it a bit more involved. Informally, the setting is the following. We have some node of interest \(\nu\) in \(\mathcal{D}\), and we are given \(\mathrm{\small rep}(P_i,Q_i)\) for \(k\) pairs \(P_i,Q_i \subseteq V\). For each pair, we also have a demand: “separate” or “do not separate”. We wish to find the set \(Y\) consisting of every vertex \(v\) inside \(\nu\) that fulfills the demands: i.e., \(v\) separates every pair \(P_i,Q_i\) whose demand is “separate”, and does not separate any pair \(P_i,Q_i\) whose demand is “do not separate”.

9.3 Output-Sensitive and One-Destination Query Algorithms: Proof of 2↩︎

We now provide the proof for the failure variant of 2; the proof for the simpler insertion variant appears in 14. We first focus on [item:faster-queries-reporting-all] of 2. That is, we show a data structure of \(O(n^{1.5})\) space that, given a query of failed edge \(e = \{x,y\} \in E\), reports \(X = \{u \in V \setminus \{s\} \mid \text{u separates x,y}\}\) within \(O(|X| \log^3 n)\) time.

The data structure construction augments the previous \(O(n)\) data structures for Query [query-Q1] (18) and Query [query-Q2] (26), by adding also the \(O(n^{1.5})\) space structures for ancestry/LCA queries in \(\mathcal{D}\) from 31 and for the extensions of the representative framework from [lem:rep-framework-one-vertex,lem:blackbox-reporting-all]. We will also use additional \(O(|\mu| \log |\mu|)\) space for each node \(\mu\) of \(\mathcal{D}\), and hence only \(O(n \log n)\) additional space in total, as will be explained shortly (in the discussion after 34).

9.3.0.1 Treating Exclusive Ancestors.

We start by executing a multi-source BFS from \(\mathcal{D}(x),\mathcal{D}(y)\) in the reverse of \(\mathcal{D}\), that keeps exploring the edges of a reached node only if it is not a common ancestor of \(\mathcal{D}(x),\mathcal{D}(y)\), which is checked within \(O(1)\) using 31. The “halting nodes” where this condition doesn’t hold are precisely the LCAs of \(\mathcal{D}(x),\mathcal{D}(y)\), which are at most two by 3. Except for the LCAs, the BFS visits precisely those “exclusive ancestors” from 3.1, i.e., ancestors of exactly one of \(\mathcal{D}(x),\mathcal{D}(y)\)). As explained there, all vertices in these nodes belong to \(X\). Because each node in \(\mathcal{D}\) has at most two parents, the number of edges that this BFS-in-reverse touches is at most twice the number of nodes it reaches. Therefore, this procedure reports all those vertices of \(X\) found in exclusive ancestors within \(O(X)\) time. All other vertices in \(X\) are found in ancestors of the LCAs, as explained in 3.1, and finding these becomes our main goal.

So, from now on we focus on an LCA \(\mu\) of \(\mathcal{D}(x),\mathcal{D}(y)\). We can also ensure that the BFS procedure above finds two children of \(\mu\) which are ancestors of \(\mathcal{D}(x)\) and of \(\mathcal{D}(y)\), and hence allows us to determine the anchors \(z_x,z_y\) of \(x,y\) w.r.t.\(\mu\) by [def:32anchors]. Given the equivalence of the anchors to \(x,y\) from 17, our problem now reduces to the following task: Given \(e = \{x,y\} \in E\), an LCA \(\mu\) of \(\mathcal{D}(x),\mathcal{D}(y)\), and the anchors \(z_x,z_y\) of \(x,y\) w.r.t.\(\mu\), we wish to report the set \(X^\mu : = \{u \in \mathcal{D}^{\uparrow}(\mu) \mid \text{u separates z_x,z_y}\}\) in \(\tilde{O}(|X^{\mu}|)\) time. Since this is our only focus, and in order to avoid clutter, from now on we will slightly abuse notation and write \(X\) instead of \(X^\mu\).

9.3.0.2 \(\mathrm{\small rep}(\cdot)\) for Proper Paths.

We will need some additional notions regarding proper paths in the skeleton \(\mathcal{H}_\mu\). Let \(P\) be such a proper path with endpoint nodes \(a\) and \(b\). Vertex \(u\) is said to separate \(P\) if \(u\) separates the associated terminal sets \(\mu(a,P),\mu(b,P)\) of \(P\) (which have been defined in 3). That is, there exists a \(u,s\)-mincut which keeps \(\mu(a,P)\) on one side, and \(\mu(b,P)\) on the other side. (Note that a single skeleton edge is trivially also a proper path.) We define the representative information of \(P\) as a shorthand to the representative information of its associated terminal sets, and write this as \(\mathrm{\small rep}(P) := \mathrm{\small rep}(\mu(a,P), \mu(b,P))\). We have the following easy consequence of 7 and 4:

We store the \(O(|\mu| \log |\mu|)\) data structure of 11 for the skeleton \(\mathcal{H}_\mu\), where the information associated with a proper path is \(\mathrm{\small rep}(P)\). So, when queries with the two endpoints of a proper path, this data structure returns a partition of the path into \(O(\log |\mu|)\) subpaths (specified by their endpoints), along with \(\mathrm{\small rep}(\cdot)\) for each of these subpaths. Additionally, we will store the \(O(|\mu|)\) data structure of 10, which lets us determine the order of nodes on a proper path. So, over all nodes, this only adds \(O(n \log n)\) additional storage, which is negligible as we already use \(O(n^{1.5})\) storage.

9.3.0.3 Restriction to Specific Node.

Let us focus on a specific node \(\nu\) which is an ancestor of \(\mu\), and suppose we just wish to find \(X_\nu := X \cap \nu\), i.e., all those vertices in \(\nu\) that separate \(z_x,z_y\), in \(\tilde{O}(X_\nu)\) time. Thus, \(\nu\) consists of all those vertices \(u \in \nu\) that would have been reported by one the query algorithms for Query [query-Q1] from [sec:splitting-mu], or for Query [query-Q2] from 8. Denote by \(X_\nu^{(1)}\) and \(X_\nu^{(2)}\) the respective sets of vertices in \(X\), so \(X_\nu = X_\nu^{(1)} \cup X_\nu^{(2)}\). Thus, it suffices to report each \(X_\nu^{(i)}\) in time \(\tilde{O}(|X_\nu^{(i)}|)\). From now on, we focus on the more complicated Query [query-Q1], as the procedure for [query-Q2] is very similar (and much simpler). Let us consider the steps of the query algorithm, and the way these are modified to obtain our goal.

First, Step 0 has already been executed, as we have found \(z_x,z_y\) before. Next, if Step 1 fails, i.e. \(\lambda_\mu \neq c(R(\mu))\) or \(\phi_\mu (z_x) = \phi_\mu (z_y)\), we know \(X_\nu^{(1)} = \emptyset\), and we are done.

We “simulate” Step 2 by the following procedure. We have stored the endpoints of the projection paths \(\pi_\mu (z_x)\) and \(\pi_\mu (z_y)\). By a query to the data structure of 10 for \(\mathcal{H}_\mu\), we get their order on \(\pi_\mu (e)\). This allows us to determine the endpoints of the middle/overlap/prefix/suffix subpaths of \(\pi_\mu (e)\). For each such subpath \(P\), we use the data structure from 11 which we have stored for \(\mathcal{H}_\mu\) (with \(I(\cdot) = \mathrm{\small rep}(\cdot)\)) to get a partition of \(P\) to \(O(\log n)\) paths \(P_1,P_2,\dots\), along with \(\mathrm{\small rep}(P_i)\) for each \(i\). We call \(P_1,P_2, \dots\) the parts of \(P\). We do not yet use their \(\mathrm{\small rep}(\cdot)\)-s, but “save” them for later usage. So, this modified Step 2 takes us only \(O(\log n)\) time.

Step 3 can be executed in exactly the same manner as before, except we do not compute the sets \(A_\mu (z_x)\) and \(A_\mu (z_y)\), but rather just “save” their corresponding representative information, i.e., \(\mathrm{\small rep}(A_\mu (z_x)) := \mathrm{\small rep}(\mu_i (z_x) \cup \{x\}, \mu_{1-i} (z_x))\) for \(A_\mu (z_x)\) and \(\mathrm{\small rep}(A_\mu (z_y)) := \mathrm{\small rep}(\mu_j (z_x) \cup \{x\}, \mu_{1-j} (z_x))\) for the next step, which is the most crucial.

We now arrive at the key Step 4. To demonstrate the essence, suppose that we just want to report all those vertices from \(X^{(1)}_\nu\) which would have been reported in Substep 4c; similar arguments apply to each of the other substeps. Thus, our goal is to report all those vertices \(u \in \nu\) such that:

1. \(u\) belongs to either \(A_\mu (z_x)\) or \(A_\mu (z_y)\),

2. \(u\) separates some edge in the prefix or in the suffix, and

3. \(u\) does not separate any edge in the middle/overlap.

To this end, iterate over all possible choices of \(A \in \{A_\mu (z_x), A_\mu (z_y)\}\) and part \(P_i\) of either the prefix or the suffix. In each such iteration, we apply 33 to find all vertices in \(\nu\) that (1) belong to \(A\), (2) separate \(P_i\) (or equivalently, separate some edge in \(P_i\), by 34), and (3) do not separate any of the \(O(\log n)\) parts of the middle/overlap. Namely, the input for 33 is the list that starts with \(\mathrm{\small rep}(A)\), \(\mathrm{\small rep}(P_i)\), followed by \(\mathrm{\small rep}(\cdot)\) of each part of the prefix/suffix (and \(\ell = 2\)).

These are a total of \(O(\log n)\) calls to 33, where each call is applied on \(O(\log n)\) \(\mathrm{\small rep}(\cdot)\)’s, thus taking \(O(\text{\# vertices returned} + \log^2 n)\) time. The union of the vertices returned by each of these calls is precisely the set of vertices from \(\nu\) that would have been reported in Substep 4c. Thus, the time it takes us to report this union is proportional to its size, up to a multiplicative \(\log n\) factor, plus an additive \(\log^3 n\) term.

As previously mentioned, a similar analysis applies to every other substep of Step 4 for Query [query-Q1], and a simpler one applies to Query [query-Q2]. We thus get the following:

9.3.0.4 Finding The Relevant Nodes.

We are now ready to explain how we find the set \(X\) consisting of every \(u \in \mathcal{D}^{\uparrow}(\mu)\) which separates \(z_x,z_y\) in time \(\tilde{O}(X)\).

Call a node \(\nu\) which is an ancestor of \(\mu\) relevant if it contains a vertex from \(X\), i.e., if \(X_\nu = X \cap \nu \neq \emptyset\). If we somehow knew all the relevant nodes, we could have just applied the query of 2 on each of them, and return the union of found vertices, which is precisely \(X\), and this would take \(\tilde{O}(X)\) time. So, our goal is to find these relevant nodes without spending much time looking into irrelevant ones.

To this end, we execute the following BFS-like procedure, which works by visiting nodes \(\nu\) of \(\mathcal{D}\), where in such a visit reports the set \(X_\nu\) and marks \(\nu\) as visited. We initialize a queue \(\mathcal{Q}\) to contain \(\mu\), and the following iterations while \(\mathcal{Q} \neq \emptyset\):

• Dequeue node \(\nu\) from the front of \(\mathcal{Q}\).

• If \(\nu\) is not marked as visit it, visit \(\nu\) as follows:

  • Find and report \(U_\nu\) using 2.

  • Mark \(\nu\) as visited.

  • If \(\nu\) is relevant (i.e., \(U_\nu \neq \emptyset\)), enqueue its (at most two) parents.

To prove correctness, we should show that this procedure indeed visits all the relevant nodes. Let \(\nu\) be a relevant node, and let \((\nu = \nu_0, \nu_1, \dots, \nu_k = \mu)\) be a path from \(\nu\) to \(\mu\) in \(\mathcal{D}\). Using the insights behind the representative framework from 5, we can show that every \(\nu_i\) on this path must be relevant. Indeed, because \(\nu = \nu_0\) is useful, i.e., contains a vertex which separates \(z_x,z_y\), by 14 it must be a descendant of some representative node \(\eta\) for \((z_x,z_y)\) or for \((z_y,z_x)\). Thus, every other \(\nu_i\) is a strict descendant of \(\eta\), and as \(\mu\) is a descendant of \(\nu_i\), we have have \(z_x,z_y \in \mathcal{D}_{\downarrow}(\mu) \subseteq \mathcal{D}_{\downarrow}(\nu_i)\). Therefore, by 14, every vertex in \(\nu_i\) must separate \(z_x,z_y\), and in particular \(\nu_i\) is relevant. Now, as the procedure starts by visiting \(\mu = \nu_k\), it must find that it is relevant and enqueue \(\nu_{k-1}\), and so it must also visit \(\nu_{k-1}\), find that it is relevant and enqueue \(\nu_{k-2}\), and so on until \(\nu_0 = \nu\) is visited. Finally, as each visit to a relevant node causes at most two enqueue operations, and visits to irrelevant nodes do not cause any enqueues, the number of visited node is bounded by at most twice the number of relevant nodes, which is at most \(X\). A visit to node \(\nu\) takes \(O(|X_\nu| \log n + \log^3 n)\) time. Hence, the total running time is \(O(\sum_\nu |X_\nu| \log n + |X| \log^3 n) = O(|X| \log n + |X| \log^3 n) = O(|X| \log^3 n)\).

This concludes the proof of (the failure variant) of 2(1).

9.3.0.5 One Destination Queries.

We now discuss [item:faster-queries-one-vertex] of 2, where a query consists of failed edge \(e = \{x,y\} \in E\) and destination \(u \in V \setminus \{s\}\), and we should determine whether the \(u,s\)-mincut value decreases after the failure of \(e\), or equivalently, whether \(u\) separates \(x,y\).

The data structure is the same as for [item:faster-queries-reporting-all].

To answer the query, we first determine the ancestry relations between \(\mathcal{D}(u)\) and \(\c(x),\mathcal{D}(y)\), which takes \(O(1)\) time using 31. As discussed in 3.1, the only case where this does not suffice is when \(\mathcal{D}(u)\) is an ancestor of both. Next, using 31, we find the (at most two) LCAs of \(\mathcal{D}(x),\mathcal{D}(y)\) within \(O(\log n)\) time. For each LCA \(\mu\), we also get two children of it which are ancestors of \(\mathcal{D}(x)\) and of \(\mathcal{D}(y)\), and hence we know the anchors of \(x,y\) w.r.t.\(\mu\) (by [def:32anchors]). By two more ancestry queries, we find one LCA \(\mu\) s.t.\(u \in \mathcal{D}^{\uparrow}(\mu)\), and let \(z_x,z_y\) be the anchors of \(x,y\) w.r.t.\(\mu\). At this point, our goal becomes to determine whether \(u\) would have been reported by the query algorithms of Query [query-Q1] or [query-Q2]; we focus on the first one, as the latter is similar but much simpler. We execute the modified steps, from Step 0 up to Step 3, exactly as we did for [item:faster-queries-reporting-all]. So, when we arrive at Step 4, we have the following:

• For each subpath \(P\) of \(\pi_\mu (e)\) among the middle/overlap/prefix/suffix, we have a partition of \(P\) into \(O(\log n)\) parts \(P_1,P_2, \cdots\), along with \(\mathrm{\small rep}(P_i)\) for each part.

• \(\mathrm{\small rep}(A_\mu (z_x)) := \mathrm{\small rep}(\mu_i (z_x) \cup \{z_x\}, \mu_{1-i} (z_x))\) and \(\mathrm{\small rep}(A_\mu (z_y)) := \mathrm{\small rep}(\mu_j (z_y) \cup \{z_y\}, \mu_{1-j} (z_y))\).

Thus, by \(O(\log n)\) calls to the representatives framework structure of 32 (each taking \(O(1)\) time), we determine for each \(P \in \{\text{middle, overlap, prefix, suffix}\}\) whether \(u\) separates \(P\) (or equivalently, by 34, separates an edge of \(P\)), and also determine whether \(u \in A_\mu (z_x)\) and whether \(u \in A_\mu (z_y)\). So we can now decide in \(O(1)\) time whether to report \(u\), by exactly the same logic of Step 4 from [sec:splitting-mu].

This concludes the proof of [item:faster-queries-one-vertex] of 2.

9.4 Output-Sensitive Queries for All-Pairs Mincuts: Proof of 3↩︎

We now prove 3, and show a data structure with \(O(n^{2.5})\) space that, given a query of failed edge \(e = \{x,y\}\), reports the set \(X\) of all vertex pairs \(u,w\) such that the \(u,w\)-mincut value changes after the failure of \(e\), within \(O(|X| \log^3 n)\) time. We store, for every \(s \in V\) the single-source data structures of 2 corresponding to this source \(s\), so the space is clearly \(O(n^{2.5})\). The key insight is:

This leads to the following query algorithm: First, using the data structures for \(x\) and for \(y\) as the sources, find all vertices \(u\) such that either the \(u,x\)-mincut value or the \(u,y\)-mincut value decreases after the failure of \(e\). Let \(U\) be the set of all such vertices \(u\) that were found. Then, for every \(u \in U\), use the data structure for \(u\) as the source to find all vertices \(w\) such that the \(u,w\)-mincut value decreases after the failure of \(e\). Let \(W_u\) be the set of all such vertices \(w\) that were found. Report \(X\) as the set of pairs \(u,w\) such that \(w \in W_u\).

The correctness follows immediately from 35. As for the running time: The first step takes us \(O(|U| \log^3 n)\) time, and the second \(O(\sum_{u \in U} |W_u|\log^3 n)\) time. Note that, by definition of \(U\), for each \(u \in U\), \(W_u\) contains at least one of \(x\) or \(y\), hence \(|U| \leq \sum_{u \in U} |W_u|\). Also, this last sum counts every pair from \(X\) at most twice. Thus, the running time of the query algorithm is \(O(|X| \log^3 n)\).

10 Examples for Key Structures↩︎

10.1 Connectivity Carcass↩︎

7 gives an example of the connectivity carcass, formally introduced in 2.1.

• Numbers next to edges in \(G\) represent their multiplicities (no number means multiplicity \(1\)). The terminals in \(S\) and non-terminals in \(V \setminus S\) are denoted by capital and lowercase letters, respectively. The capacity of \(S\)-mincuts is \(\lambda_S = 6\).

• Each terminal vertex is mapped to a node in \(\mathcal{H}_S\), but the mapping is neither injective (two terminals can go in the same node, as terminals \(H,I\) in this example) nor surjective (there are empty nodes).

• The dashed colored lines show several canonical cuts of \(\mathcal{H}_S\). Canonical cuts bijectively correspond to valid partitions of \(S\), but such a valid partition can be induced by many different \(S\)-mincuts. The two red \(S\)-mincut in \(G\) both give rise to the same valid partition \(\{R,T\}, S \setminus \{R,T\}\), and hence to the same canonical cut in \(\mathcal{H}_S\) (the tree-edge between the nodes with \(Q\) and with \(R\)). These two cuts keep the non-terminal \(u\) on different sides, so this valid partition (and its canonical cut) distinguishes \(u\).

• Projections of several non-terminal vertices are depicted on the right. Vertex \(z\) is non-stretched (i.e., not distinguished by any canonical cut), so \(\pi_S (z)\) is a tree node with \(G\) of \(\mathcal{H}_S\). Vertices \(u,v,w,x,y\) are stretched, so their projections are proper paths. The canonical cuts that distinguish a stretched vertex are precisely those that keep the endpoints of the projection path on different sides.

• The projection of an edge (that contributes to some \(S\)-mincut) is the unique proper path whose prefix and suffix are the projections of its endpoints, so we easily see \(\pi_S (\{u,v\})\) and \(\pi_S (\{x,y\})\).

  • For \(\{u,v\}\), the prefix and suffix \(\pi_S (u), \pi_S (v)\) are not the same, so we can easily determine the \(u\)-endpoint and the \(v\)-endpoint of \(\pi_S (\{u,v\})\) as the nodes containing \(R\) and \(M\) respectively.

  • For \(\{x,y\}\), the \(x\)-endpoint and \(y\)-endpoints are the node with \(A\) and \(F\), respectively. This can be verified through the unidirectionality property: indeed, \(\{x,y\}\) contributes to the purple \(S\)-mincut, and this cut keeps \(x\) on the same side of \(A\), and \(y\) on the same side as \(F\).

  Finally, consider again the valid partition \(\{R,T\}, S\setminus \{R,T\}\). Since its corresponding canonical cut is an edge from \(\pi_S (\{u,v\})\), it distinguishes \(e\), which means that some \(\{R,T\}, S\setminus \{R,T\}\)-mincut has \(\{u,v\}\) as a contributing edge. However, there could be \(\{R,T\}, S\setminus \{R,T\}\)-mincuts where \(\{u,v\}\) is not contributing. This is demonstrated by the two red cuts: \(\{u,v\}\) contributes to one but not the other.

10.2 Nearest Mincut Tree and Farthest Mincut DAG↩︎

8 gives an example of nearest mincut tree \(\mathcal{T}\) and the farthest mincut DAG \(\mathcal{D}\), which are presented in 3.1.

• Numbers next to edges in \(G\) represent their multiplicities (no number means multiplicity \(1\)). The source \(s\) is marked in orange.

• The minimal region defined by a dashed-red curve (resp., solid blue curve) which contains vertex \(u\) is \(\mathsf{Near}(u,s)\) (resp., \(\mathsf{Far}(u,s)\)). The red-bounded regions corresponding to nearest mincuts are laminar: every two are either disjoint, or one contains the other. The blue-bounded regions corresponding to farthest mincuts are not laminar.

• The nodes of the nearest mincut tree \(\mathcal{T}\) (resp., farthest mincut DAG \(\mathcal{D}\)) partition \(V\), where the root node contains only \(s\). For every vertex \(u\), its nearest mincut \(\mathsf{Near}(u,s)\) (resp., farthest mincut \(\mathsf{Far}(u,s)\)) consists of all the vertices found in descendants of the node \(\mathcal{T}(u)\) (resp., \(\mathcal{D}(u)\)) that contains \(u\).

11 Proofs for Preliminaries↩︎

12 Proofs for Carcass Tools↩︎

13 Lower Bounds↩︎

In this section, we present two information-theoretic lower bounds on space for our data structure in 1. Our first lower bound is in undirected graphs for fixed \(s,t\)-mincut, and the second lower bound is in directed graphs for single-source mincuts.

13.0.0.1 Undirected graphs with fixed source-sink mincut

13.0.0.2 Directed graphs with single-source mincuts

The following is an immediate corollary of 11.

14 Output-Sensitive and One-Destination Queries for Edge Insertion↩︎

In this section, we prove the insertion variant of 2. The data structure (for both items of 2) stores the nearest mincut tree \(\mathcal{T}\) and the farthest mincut DAG \(\mathcal{D}\) along with data structures that support constant-time ancestry queries for both. For \(\mathcal{T}\), we can use any of-the-shelf \(O(n)\) space ancestry data structure (e.g. [40]). For \(\mathcal{D}\), we use the \(O(n^{1.5})\) space data structure from 31. Thus, the total space is \(O(n^{1.5})\).

We start with the simple query algorithm for [item:faster-queries-one-vertex]: given an inserted edge \(e = \{x,y\}\) and vertex \(u \in V \setminus \{s\}\), we wish to determine whether the \(u,s\)-mincut value increases after \(e\) is inserted, within \(O(1)\) time. As discussed in 3.1, this happens iff \(u \in \mathcal{T}^{\uparrow}(x) \setminus \mathcal{D}^{\uparrow}(y) \cup \mathcal{T}^{\uparrow}(y) \setminus \mathcal{D}^{\uparrow}(x)\). To detect this situation, we just need to determine the ancestry relations between \(\mathcal{T}(u)\) and \(\mathcal{T}(x),\mathcal{T}(y)\), and between \(\mathcal{D}(u)\) and \(\mathcal{D}(x),\mathcal{D}(y)\), which we can do within \(O(1)\) time using the ancestry data structures.

We now focus on the query algorithm for [item:faster-queries-reporting-all]: given an inserted edge \(e = \{x,y\}\), we wish to report the set \(X\) of all vertices \(u \in V \setminus \{s\}\) such that the value of \(u,s\)-mincut increases after \(e\) is inserted, within \(O(|X|)\) time. For this, we use ideas introduced by [3]. We first observe the following:

Recall that, by the previous discussion, \(X = \mathcal{T}^{\uparrow}(x) \setminus \mathcal{D}^{\uparrow}(y) \cup \mathcal{T}^{\uparrow}(y) \setminus \mathcal{D}^{\uparrow}(x)\). So, by 12, we conclude that for any node \(\nu\) of \(\mathcal{T}\), either \(\nu \cap X\) is all of \(\nu\), or it is \(\emptyset\); we call \(\nu\) relevant if the former holds. Also, 12 implies that \(X_1 = \mathcal{T}^{\uparrow}(x) \setminus \mathcal{D}^{\uparrow}(y)\) and \(X_2 = \mathcal{T}^{\uparrow}(y) \setminus \mathcal{D}^{\uparrow}(x)\) are disjoint: indeed, if \(v \in X_1\) then \(\mathcal{T}(v)\) is an ancestor of \(\mathcal{T}(x)\), so \(\mathcal{D}(v)\) is an ancestor of \(\mathcal{D}(x)\), and thus \(v \notin X_2\). We now arrive at the key insight of [3]:

We thus get the following query algorithm: Find all relevant nodes in \(\mathcal{T}\) by walking upwards, once from \(\mathcal{T}(x)\) and once from \(\mathcal{T}(y)\); whenever a node is encountered in the walk, check if it is relevant within \(O(1)\) time by using \(O(1)\) ancestry queries in \(\mathcal{T}\) and \(\mathcal{D}\), and halt if an irrelevant node is reached. This procedure visits at most two irrelevant nodes and all the useful nodes, which are at most \(O(|X|)\); then, we report the set \(X\) of all vertices inside the relevant nodes, which again takes \(O(|X|)\) time.

References↩︎

---

1. Weizmann Institute of Science, Israel. Email: koustav.bhanja@weizmann.ac.il. Supported by the Koshland Prize fellowship, and Merav Parter’s European Research Council (ERC) grant under the European Union’s Horizon 2020 research and innovation programme, grant agreement No. 949083.↩︎

2. Weizmann Institute of Science, Israel. Email: merav.parter@weizmann.ac.il. Supported partially by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement No. 949083.↩︎

3. Weizmann Institute of Science, Israel. Email: asaf.petruschka@weizmann.ac.il. Supported by an Azrieli Foundation fellowship, and by Merav Parter’s European Research Council (ERC) grant under the European Union’s Horizon 2020 research and innovation programme, grant agreement No. 949083.↩︎

4. More accurately, the improvement would be to [item:faster-queries-reporting-all] of 2; for [item:faster-queries-one-vertex] we also need fast LCA queries on the DAG, which are more general than just reachability.↩︎

5. A trivial extension of 2(2) incurs an additional \(O(n)\) time to report all affected pairs from \(V\times V\).↩︎

6. Usually, a cactus only means that no edge is shared by two cycles, but we only deal with cacti having node-disjoint cycles.↩︎

7. The mapping \(\pi_S (\cdot)\) need not be surjective, i.e., there could be nodes of \(\mathcal{H}_S\) without mapped terminals.↩︎

8. If \(x\) is non-stretched, this means that the node \(\pi_S (x)\) is the \(x\)-endpoint of \(\pi_S (e)\), and similarly with \(y\).↩︎

9. Here and througout, “to separate \(x,y\)” is shorthand for “to separate \(\{x\},\{y\}\)”.↩︎

10. For a node \(\mu\), we naturally denote \(\mathcal{D}^{\uparrow}(\mu)\) and \(\mathcal{D}_{\downarrow}(\mu)\) for the sets of vertices in ancestors and in descendants of \(\mu\), respectively.↩︎

11. Similarly to trees, an LCA of two nodes in a DAG is a common ancestor of them, which does not have any child that is also a common ancestor. Unlike trees, there could be several LCAs, but they must be unrelated by ancestry.↩︎

12. A level-ancestor query gets node \(a\) and non-negative integer \(d\), and returns the ancestor of \(a\) that has depth \(d\) (or a null value if \(a\) has depth smaller than \(d\).)↩︎