Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, and Optimal Sensitivity Oracle

Surender Baswana, Koustav Bhanja

Let G be a directed weighted graph (DiGraph) on n vertices and m edges with source s and sink t. An edge in G is vital if its removal reduces the capacity of (s,t)-mincut. Since th…