BARC Talk by Marcin Pilipczuk

Abstract:

At STOC 2022, we proposed a new algorithmic technique for graph separation problems in directed graphs, called flow-augmentation.

It turned out to be the missing piece in the toolbox for parameterized algorithms: it not only led to immediate resolution of a few open problems in the area, but also completed a parameterized dichotomy of MinSAT CSPs over the boolean domain, parameterized by the number of unsatisfied constraints, and was a crucial ingredient in proving fixed-parameter tractability of Directed Multicut with three terminal pairs.

Further applications for CSPs over temporal and interval domains were very recently discovered. During the talk, I will introduce the technique, show example application, and survey the results.