Directed flow-augmentation
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström · 2022
We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph G, two integers s,t ∈ V(G), and an integer k, adds (randomly) to G a number of arcs such that for every minimal st-cut Z in G of size at most k, with probability 2−poly(k) the set Z becomes a minimum st-cut in the resulting graph.