← 研踪 PaperTrailarXiv:2607.00894 · v2
Space-Optimal Sensitivity Oracles for Single-Source Mincuts
首次提交 2026-07-01 21:00
版本更新 2026-11-05 22:12
雷达观测 2026-11-06 12:09
摘要
How much information is needed to describe the effect of any single edge failure on all mincuts? Classical mincut representations, such as Gomory-Hu trees and cactus-like structures, show that mincuts often admit unexpectedly compact static certificates. However, much less is known about whether such compactness survives failures. We study the single-source setting. Given an undirected multigraph $G$ and source $s$, our oracle reports, for any failed edge $e$, all vertices $t$ whose $s,t$-mincut value decreases in $G\setminus{e}$; equivalently, whether $e$ belongs to some $s,t$-mincut. This is the single-source analogue of Picard-Queyranne's fixed-pair [MPS '80] and Baswana-Pandey's all-pairs sensitivity results [SODA '22], and the failure counterpart of Baswana-Gupta-Knollmann's insertion oracle [Algorithmica '22]. No subquadratic-space solution was known to date. We give an optimal $O(n)$-space oracle with $O(n)$ reporting time, matching the insertion bounds. We also give $O(n^{1.5})$-space oracles for insertions and failures, with $O(\log n)$ membership queries or amortized $O(\log^2 n)$ reporting time per affected vertex. Subquadratic-space oracles with such fast query times were unknown, even for insertions. Our main technical contribution connects farthest mincut DAGs, central to the insertion oracle, with Dinitz-Vainshtein's Connectivity Carcass for Steiner mincuts [STOC '94], which generalizes global-mincut cactus representations. These novel, intricate connections reveal the carcass's potential beyond Steiner mincuts.
作者备注：fixed and improved output-sensitive query
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-05 22:12 · 最新观测版本
Space-Optimal Sensitivity Oracles for Single-Source Mincuts
How much information is needed to describe the effect of any single edge failure on all mincuts? Classical mincut representations, such as Gomory-Hu trees and cactus-like structures, show that mincuts often admit unexpectedly compact static certificates. However, much less is known about whether such compactness survives failures. We study the single-source setting. Given an undirected multigraph $G$ and source $s$, our oracle reports, for any failed edge $e$, all vertices $t$ whose $s,t$-mincut value decreases in $G\setminus{e}$; equivalently, whether $e$ belongs to some $s,t$-mincut. This is the single-source analogue of Picard-Queyranne's fixed-pair [MPS '80] and Baswana-Pandey's all-pairs sensitivity results [SODA '22], and the failure counterpart of Baswana-Gupta-Knollmann's insertion oracle [Algorithmica '22]. No subquadratic-space solution was known to date. We give an optimal $O(n)$-space oracle with $O(n)$ reporting time, matching the insertion bounds. We also give $O(n^{1.5})$-space oracles for insertions and failures, with $O(\log n)$ membership queries or amortized $O(\log^2 n)$ reporting time per affected vertex. Subquadratic-space oracles with such fast query times were unknown, even for insertions. Our main technical contribution connects farthest mincut DAGs, central to the insertion oracle, with Dinitz-Vainshtein's Connectivity Carcass for Steiner mincuts [STOC '94], which generalizes global-mincut cactus representations. These novel, intricate connections reveal the carcass's potential beyond Steiner mincuts.
查看此版本解读 →查看此版本原文 ↗