在本研究中，我们探讨了单源最小割灵敏度神谕，这是一种紧凑的数据结构，可以在查询某条边 $e$ 时，报告因插入或删除 $e$ 而导致其到源点 $s$ 的最小割值发生变化的受影响顶点。插入查询已由 Baswana、Gupta 和 Knollmann 在其作品中处理，展示了仅需 $O(n)$ 空间的极其紧凑的神谕。
我们关注边删除查询，这一问题更具挑战性且更为重要。目前的最佳方法需要 $O(n^2)$ 空间：要么使用 $n-1$ 个固定对神谕，每个 $O(n)$ 空间，基于 Picard-Queyranne 表示，要么使用 Baswana 和 Pandey 提出的 $O(n^2)$ 空间的全对神谕。
我们的关键结果是为边删除查询提供了一个最优的 $O(n)$ 空间单源最小割灵敏度神谕。该神谕能在 $O(n)$ 时间内报告受影响的顶点集合，从而与插入情况的最新界限相匹配。此外，我们提供了查询时间接近最优的神谕，代价是空间增加到 $O(n^{1.5})$。这些神谕能够在 $O(\log n)$ 时间内确定任何给定顶点是否受到边的插入/删除影响，或在每个顶点的摊销 $O(\log^3 n)$ 时间内报告所有受影响的顶点。此前，甚至对于插入，这种亚二次空间的神谕都是未知的。
我们主要的技术贡献是在两个看似遥远的对象之间建立新颖而复杂的联系，这两个对象分别代表了不同的最小割家族。第一个是到源的最远最小割的有向无环图（DAG）表示，这是 Baswana、Gupta 和 Knollmann 引入的核心工具。第二个是 Dinitz 和 Vainshtein 提出的 Steiner 最小割的连接尸体（Connectivity Carcass），它很好地推广了全球最小割的著名仙人掌表示。我们的工作展示了连接尸体在超出其明显的 Steiner 最小割范围之外的相对未被探索的潜力。
博主点评： 本文在最小割灵敏度神谕的研究上取得了重要进展，尤其是在边删除查询方面的空间优化，展示了新的方法论和技术联系，值得在更广泛的图论和网络流领域进行深入研究。