Directed flow-augmentation

We show a ow-augmentation algorithm in directed graphs: ere exists a randomized polynomial-time algorithm that, given a directed graph G, two vertices 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. We also provide a deterministic counterpart of this procedure. e directed ow-augmentation tool allows us to prove xed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set, whose parameterized complexity status was repeatedly posed as open problems: *