Flow-augmentation I: Directed graphs
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström · Journal of the ACM · 2024
We show a flow-augmentation algorithm in directed graphs: There 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. The directed flow-augmentation tool allows us to prove fixed-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: Chain SAT , defined by Chitnis, Egri, and Marx [ESA’13, Algorithmica’17], a number of weighted variants of classic directed cut problems, such as Weighted st - Cut or Weighted Directed Feedback Vertex Set . By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H , if the List H - Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable.