Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs

The first result we discuss pertains to the max-flow problem in directed graphs. To date, no efficient sensitivity oracles for max-flow are known, even for handling a single edge failure. While it is possible to determine efficiently whether the $(s,t)$-max-flow value decreases after an edge failure – thanks to the work of Picard and Queyranne [50], which yields an $O(n)$-sized data structure with $O(1)$ query time (see Theorem 4.6 of [4]) – the problem of efficiently reporting the updated $(s,t)$-max-flow after an edge failure remains unresolved. The complexity of this problem arises from the potential need to reroute flow through an alternative path in the residual graph, especially if the failed edge was carrying flow in the original $(s,t)$-max-flow of $G$.

To tackle this, we first demonstrate that for any directed graph $G$, there exists a small family of flows that effectively captures the maximum flows of the graph $G-e$ for all potential edge failures $e\in E$. Specifically, we obtain the following result.

We further prove an $\mathrm{\Omega }(n)$ lower bound on the cardinality of $ℬ$, independent of $\lambda$, for $k⩾2$ failures.

It is important to note that the above theorem provides a compact flow family resilient to a single edge failure, which can be amenable to various algorithmic applications. However, it does not directly imply a compact data structure for efficiently reporting the maximum flow in a fault-prone network. We thus ask the following question.

To the best of our knowledge, this problem has not been addressed in the existing literature. We answer this question affirmatively by presenting the following sensitivity oracle for handling both single and dual edge failures, which leverages the flow-covering result from Theorem 1.1.

We note that the bound in Theorem 1.2 is essentially tight, as $\mathrm{\Omega }(\lambda n)$ is also a lower bound on the number of edges required to represent a maximum flow from source to sink.

We next discuss our result on min-cut sensitivity oracle for two edge failures. Baswana et al. [4] presented an $O(n^2)$-sized data structure to answer min-cut queries after two edge failures in $O(1)$ time. They also gave a conditional lower bound of $\tilde{\mathrm{\Omega }}(n^2)$ on the oracle size, based on the Directed Reachability Hypothesis. Recently, Bhanja [10] improved this lower bound by proving an unconditional bound of $\mathrm{\Omega }(n^2)$ on the size of the oracle. This lower bound holds for directed as well as undirected graphs.

Given that the result of [4] has a matching upper and lower bound of $\mathrm{\Theta }(n^2)$, any improvement to the dual edge failure oracle seems unlikely. However, in many applications, the focus is towards networks with cuts of small size. Similar scenarios have been previously studied by Abboud et al. [1], Akmal and Jin [2] for finding all pairs of vertices in graphs with small edge connectivity. This naturally raises the following question.¹¹1We remark that the data-structure of [4] takes quadratic size even when $\lambda =1$. For details, see the full version.

We answer this question in the affirmative by presenting the following result, where the size of the oracle scales linearly with the min-cut size $\lambda$.

Our min-cut oracle for dual failures employs a different set of tools compared to those in [4]. In particular, we show the robustness of our flow-covering result of Theorem 1.1 by combining it with the seemingly unrelated 1-fault-tolerant strong-connectivity oracle of Georgiadis et al. [34], that takes linear space and answers strong-connectivity queries after single edge failure in constant time. This combination not only allows us to design an alternate min-cut sensitivity oracle but also introduces a new set of ideas which are of independent interest.

We further show that the bound of $\lambda n$ on the size of the oracle in Theorem 1.3 is tight by presenting the following result.

We now discuss the problem of designing fault-tolerant min-cut oracle for graphs under the general setting of up to $k$ failures. Our goal is to construct an oracle of $F(k,\lambda )\cdot o(n^2)$ space and $F^{\prime }(k,\lambda )$ query time. Before presenting our results for this scenario, it is essential to set the context by discussing a broader landscape.

The task of building a $k$-fault-tolerant $(s,t)$-min-cut oracle is notably more complex than designing a $k$-fault-tolerant $(s,t)$-reachability oracle²²2This is because $(s,t)$-reachability can be reduced to $(s,t)$-min-cut by adding a dummy source with an out-edge to the original source, limiting the maximum flow to one.. At present, optimal-size $(s,t)$-reachability oracles in the fault-tolerant setting have been achieved only for single and dual failures. See Table 1 for a brief summary of existing results. For $k=1$, the dominator trees introduced by Lengauer and Tarjan [45] provides a linear-size data structure with constant query time. Choudhary [17] extended this by presenting an optimal dual fault-tolerant single source reachability oracle. For general $k$, the situation becomes significantly more challenging. The only currently known results are an oracle with $O(2^{k}n)$ query time due to fault-tolerant reachability preservers of [5]; and an all-pairs reachability oracle by Brand and Saranurak [56], which achieves a size of $O(n^2\log n)$ and has $O(k^{\omega })$ query time.

This naturally leads us to the following open question.

In this work, we affirmatively address this question by providing near-optimal results for $(s,t)$-reachability under any constant number of failures. In fact, we solve the more general problem of the $k$-fault-tolerant min-cut, as formalized in the following theorem.

Although the space complexity and query time of our oracle grow significantly with respect to $k$, the oracle becomes highly efficient for small values of $k$. Similar assumptions have been made in prior work. For instance, recent advancements [57, 56, 29, 41] in fault-tolerant distance oracles for undirected graphs have resulted in a breakthrough by Dey and Gupta [19] where they design an oracle with $O(k^4{n}^2)$ space and query time of ${(k\log n)}^{O(k^2)}$.

A summary of existing results on $(s,t)$-min-cut sensitivity oracles, along with our new contributions, is presented in Table 2.

As a direct consequence of Theorem 1.5, we obtain the following corollary.

Observe that a straightforward way to store edges carrying non-zero flow for each $f_i\in 𝒜$ would require $O({\lambda }^{2}n)$ space, since each flow can saturate up to $\lambda n$ edges. However, we show that it is possible to store all flows implicitly in $O(\lambda n)$ space by carefully constructing $𝒜$ such that the number of edges on which any two flows differ is linear in $n$. To handle the failure of critical edges, the family $𝒜$ is further extended to compute a compact family $ℬ$ within the same size bounds, such that $ℬ$ contains a max-flow of $G-e$ for each edge $e$, whether critical or non-critical.

Our oracle supports two types of queries:

• $\mathrm{■}$

  Flow through specific edge: Given a failing edge $e$ and a query edge $x$, determine $f_e(x)$ in $O(1)$ time, where $f_e$ is a canonical max-flow of $G-e$.

• $\mathrm{■}$

  Flow through all edges: Given a failing edge $e$, the oracle implicitly reports the updated max-flow in $O(n)$ time.

A natural extension of Theorem 1.1 is to ask whether the flow family can be generalized to handle multiple edge failures, thereby yielding max-flow sensitivity oracles for dual or higher failures. Unfortunately, this is not the case, as we prove an $\mathrm{\Omega }(n)$ lower bound on the cardinality of $ℬ$ for $k⩾2$ failures (for details see the full version).

However, we overcome this obstacle by exploiting the following key property: for any $(s,t)$-flow $f$ in $G$ with $f(e)=0$, the graph $G_f-e$ is the residual network of $(G-e)$ under $f$. Although seemingly straightforward, this observation provides a bridge between fault-tolerant flow families and our max-flow (as well as min-cut) sensitivity oracles under dual edge failures.

For instance, when edges $e,e^{\prime }$ are deleted, the updated max-flow can be efficiently obtained if there exists a maximum flow $f$ satisfying $f(e)=0$. In this case, re-routing reduces to adjusting the flow through $e^{\prime }$ using graph $G_f-e$, rather than recomputing ${(G-e)}_f$. The existence of such flows are guaranteed by the family $ℬ$. Moreover, we show that by sparsifying $G_f$ using the 1-fault-tolerant strong connectivity preservers of Georgiadis et al. [34], this re-routing can be performed in $O(n)$ time.

For a failing edge $e$, if $\tilde{f}(e)=0$ then there is no change in the flow, so we simply return $\tilde{f}(x)$. Otherwise, we use the precomputed flow $f_e$ (a max-flow in $𝒢-e$) to return $f_e(x)$. Both these steps require only $O(1)$ time due to ˜5.4. See Algorithm 1.

Consider a failing edge $e$ in $G$. If $\tilde{f}(e)=0$, then there is no change in the flow, so we simply return the empty-set. If not, we retrieve the label of flow $f_e\in ℬ$ that is an $(s,t)$-max-flow in $𝒢-e$. Next, to identify the edges over which $\tilde{f}$ and $f_e$ differ, we simply traverse the sets ${\text{null}}_{𝒢}(\tilde{f})$ and ${\text{null}}_{𝒢}(f_e)$, and output their symmetric difference. This operation takes $O(n)$ time, as by Lemma 5.2, the size of both the sets involved is at most $3n$. See Algorithm 2.

This completes our discussion on the max-flow sensitivity oracle for single failure.

Given a pair of failing edges $e$ and $e^{\prime }$, the query algorithm proceeds as follows. First, we retrieve a canonical flow $f$ in $ℬ$ that is a maximum $(s,t)$-flow in $G-e$. If this flow already avoids both failures, i.e., $f(e)=0$ and $f(e^{\prime })=0$, then it is also a maximum flow in $G-\{e,e^{\prime }\}$, and so the change in the edges carrying flow is simply $X={\text{null}}_{𝒢}(\tilde{f})\oplus {\text{null}}_{𝒢}(f)$.

Now, suppose $f(e^{\prime })=1$. By ˜5.6, we have $G_f-e$ is the residual graph of $G-e$ with respect to $f$. We next determine if there exists a directed cycle in $G_f-e$ containing ${(e^{\prime })}^{\mathrm{rev}}$, if so, we can reroute the flow along this cycle.

If, however, no such cycle exists, then flow through $e^{\prime }$ cannot be rerouted and its endpoints must belong to different strongly connected components in $G_f-e$. In this situation, we must reduce the total flow by one unit, which is achieved by canceling a unit of flow along an $(s,t)$ path that traverses $e^{\prime }$. To accomplish this, we take the help of graph $G_f+(s,t)-e$ (where a direct edge $(s,t)$ is artificially introduced). In this setting, the desired $(s,t)$ path containing $e^{\prime }$ corresponds to a cycle in $G_f+(s,t)-e$ containing edge ${(e^{\prime })}^{\mathrm{rev}}$. See Algorithm 3.

To realize the query algorithm efficiently, the only additional structure we need is, for each $f\in ℬ$, a way to detect cycles in the residual graphs $G_f-e$ and $G_f+(s,t)-e$. This is achieved by storing, for each $f$, the 1-fault-tolerant SCC preserver of Georgiadis et al. [34]. which is a subgraph with $O(n)$ edges maintaining all strongly connected components under single-edge failures. With this, checking for the existence of cycles passing through an edges takes $O(n)$ time; and this does not inflate the overall space usage.

The data structure thus consists of (a) dictionaries for $E(𝒢)$ and sets ${\text{null}}_{𝒢}(f)$ for $f\in ℬ$, and (b) the 1-FT-SCC preservers for $G_f$ and $G_f+(s,t)$ for all $f$. Since $|ℬ|=O(\lambda )$, the total space remains $O(\lambda n)$. We now discuss the time complexity of Algorithm 3. Identifying the flow $f$ just takes $O(1)$ time. Then, finding the cycle in the appropriate SCC preserver further takes $O(n)$ time, as number of edges in any FT SCC-preserver is $O(n)$. Hence, the total time to report all edges where the flows differ is $O(n)$.