Directed flow-augmentation

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. The directed flow-augmentation tool allows us to prove (randomized) 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, Weighted Directed Feedback Vertex Set, or Weighted Almost 2-SAT. By proving that Chain SAT is (randomized) 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 (with the remark that our algorithms are randomized).

Authors

• Eun Jung Kim 0002
• Stefan Kratsch
• Marcin Pilipczuk
• Magnus Wahlström

Keywords

• Chain SAT
• directed graphs
• fixed-parameter tractability
• flow-augmentation