In this study, we explore Single-Source Mincut Sensitivity Oracles, which are compact data structures that report the set of affected vertices whose mincut value to source $s$ changes upon the insertion or deletion of an edge $e$. Insertion queries were addressed by Baswana, Gupta, and Knollmann, who demonstrated an extremely compact oracle requiring only $O(n)$ space.
We focus on edge deletion queries, which are more challenging and of greater interest. The current best approaches require $O(n^2)$ space: either using $n-1$ fixed-pair oracles of $O(n)$ space each, based on the Picard-Queyranne representation, or using the $O(n^2)$ space all-pairs oracle by Baswana and Pandey.
Our key result is an optimal $O(n)$ space single-source mincut sensitivity oracle for edge deletion queries, reporting the set of affected vertices in $O(n)$ time, thus matching the state-of-the-art bounds for insertion. Additionally, we provide oracles with near-optimal query times at the cost of increasing the space to $O(n^{1.5})$. These oracles can determine if any given vertex is affected by an insertion/deletion of an edge in $O(\log n)$ time, or report all affected vertices in amortized $O(\log^3 n)$ time per vertex. Such oracles of subquadratic space were previously unknown, even for insertion.
Our main technical contribution is establishing novel and intricate connections between two seemingly distant objects representing different families of mincuts. The first is the DAG representation of farthest mincuts to the source, a central tool introduced by Baswana, Gupta, and Knollmann. The second is the Connectivity Carcass for Steiner mincuts of Dinitz and Vainshtein, which generalizes well-known cactus representations of global mincuts. Our work demonstrates the relatively unexplored potential of the carcass beyond its obvious Steiner mincuts scope.
Blogger's Review: This paper makes significant strides in the study of mincut sensitivity oracles, particularly in space optimization for edge deletion queries. It showcases novel methodologies and technical connections, warranting further exploration in the broader fields of graph theory and network flows.