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

Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, Lakshay Saggi · 2025

Read Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs by Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, Lakshay Saggi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00153.txt.

Introduction

Networks fail, and planners need to know quickly how a failure changes what can flow through them. Mridul Ahi and co-authors design fault-tolerant data structures for maximum-flow and minimum-cut problems in a 2025 study. Their setting is unweighted directed graphs with a fixed source and sink.

Sensitivity oracles answer, after an edge change, how the best flow or smallest cut is affected, without recomputing everything. Fast answers matter for transport, communication, and supply networks that must react to breakdowns. The work is theoretical computer science, aimed at data structures that stay useful when graphs are damaged. Fault tolerance here means the data structure keeps answering after parts of the graph fail.

Catalog record

CREATORMridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, Lakshay Saggi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-00153

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, Lakshay Saggi Abstract This paper addresses the problem of designing fault-tolerant data structures for the ( s , t ) (s,t) -max-flow and ( s , t ) (s,t) -min-cut problems in unweighted directed graphs. Given a directed graph G = ( V , E ) G=(V,E) with a designated source s s , sink t t , and an ( s , t ) (s,t) -max-flow of value λ \lambda , we present novel constructions for max-flow and min-cut sensitivity oracles, and introduce the concept of a fault-tolerant flow family, which may be of independent interest. Our main contributions are as follows. 1. Fault-Tolerant Flow Family: For any graph G G with ( s , t ) (s,t) -max-flow value λ \lambda , we construct a family ℬ \mathcal{B} of 2 ​ λ + 1 2\lambda+1 ( s , t ) (s,t) -flows such that for every edge e e , ℬ \mathcal{B} contains an ( s , t ) (s,t) -max-flow of G − e G-e . This covering property is tight up to constants for single failures and provably cannot extend to comparably small families for k ≥ 2 k\geq 2 , where we show an Ω ⁡ ( n ) \Omega(n) lower bound on the family size, independent of λ \lambda . 2. Max-Flow Sensitivity Oracle: Using the fault-tolerant flow family, we construct a single as well as dual-edge sensitivity oracle for ( s , t ) (s,t) -max-flow that requires only O ⁡ ( λ ​ n ) O(\lambda n) space. Given any set F F of up to two failing edges, the oracle reports the updated max-flow value in G − F G-F in O ⁡ ( n ) O(n) time. Additionally, for the single-failure case, the oracle can determine in constant time whether the flow through an edge x x changes when another edge e e fails. To the best of our knowledge, these are the first non-trivial constructions of fault-tolerant max-flow oracle. 3. Min-Cut Sensitivity Oracle for Dual Failures: Recently, Baswana et al. (ICALP’22) designed an O ⁡ ( n 2 ) O(n^{2}) -sized oracle for answering ( s , t ) (s,t) -min-cut size queries under dual edge failures in constant time, along with a matching lower bound. We extend this by focusing on graphs with small min-cut values λ \lambda , and present a more compact oracle of size O ⁡ ( λ ​ n ) O(\lambda n) that answers such min-cut size queries in constant time and reports the corresponding ( s , t ) (s,t) -min-cut partition in O ⁡ ( n ) O(n) time. We also show that the space complexity of our oracle is asymptotically optimal in this setting. 4. Min-Cut Sensitivity Oracle for Multiple Failures: We extend our results to the general case of k k edge failures. For any graph with ( s , t ) (s,t) -min-cut of size λ \lambda , we construct a k k -fault-tolerant min-cut oracle with space complexity O λ , k ​ ( n ​ log ⁡ n ) O_{\lambda,k}(n\log n) that answers min-cut size queries in O λ , k ​ ( log ⁡ n ) O_{\lambda,k}(\log n) time. This also leads to improved fault-tolerant ( s , t ) (s,t) -reachability oracles, achieving O ⁡ ( n ​ log ⁡ n ) O(n\log n) space and O ⁡ ( log ⁡ n ) O(\log n) query time for up to k = O ⁡ ( 1 ) k=O(1) edge failures. This is the first such construction to support more than two failures with near-linear space and sublinear query time, improving significantly upon previous work. 1 Introduction The increasing scale and complexity of modern networks necessitate the development of efficient algorithms for solving fundamental graph problems. Among these problems, the max-flow and min-cut problems have received significant attention due to their broad applicability in transportation networks, data propagation, resource allocation, and numerous other domains. Since the seminal work of Ford and Fulkerson [ 31 ] , extensive research has focused on computing max-flow in networks [ 30 , 36 , 35 , 23 , 44 , 42 , 55 , 32 , 54 , 12 , 8 ] , culminating in the near-linear-time algorithm by Chen et al. [ 16 ] . While the problem of computing max-flow and min-cut in a graph has been extensively studied in the past 70 years for static graphs, little is known about designing efficient data-structures for these problems for networks prone to failures. In recent years, there has been significant interest in fault-tolerant data structures, motivated by the fact that real-world networks are often vulnerable to node or link failures. In the fault-tolerant model, we assume that the total number of failures at any point remains bounded by a parameter k , which depends on the robustness of the network. Typically, k is much smaller than the total number of vertices in the network. Over the past two decades, many efficient fault tolerant data-structures have been developed for various classical graph problems, including spanners [ 46 , 21 , 47 ] , distance preservers [ 48 , 11 , 38 ] , distance oracles [ 18 , 14 , 26 , 9 ] , reachability [ 5 , 17 , 13 ] , connectivity [ 49 , 27 , 28 , 33 , 6 ] , etc. Despite these advances, the domain of max-flow and min-cut problems has seen limited progress in the context of network failures. This paper aims to address this gap by studying the problem of flows and cuts in directed networks susceptible to edge failures. We introduce simple yet powerful techniques for the aforementioned problems, which lead to state-of-the-art results for the specific problems which we study. Our objective is to compute a compact data structure, referred to as a sensitivity or fault-tolerant oracle, which, after the failure of any set of edges in the input graph G efficiently determines the max-flow and min-cut with respect to a source s and sink t . This problem is formalized as follows. Question 1 . Given a directed, unweighted graph G with a designated source s and a designated sink t , design a data-structure that given any query set of edges F\subseteq E of size k , outputs the (s,t) -max-flow and (s,t) -min-cut on deletion of edges in F from graph G . 1.1 Our Contributions Max-flow Sensitivity Oracle for Single and Dual failures 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

Read the complete text