On weighted graph separation problems and flow-augmentation

One of the first application of the recently introduced technique of \emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of $\text{textsc}DirectedFeedbackVertexSet$, a landmark problem in parameterized complexity. In this note we explore applicability of flow-augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following. – In weighted undirected graphs $\text{textsc}Multicut$ is FPT, both in the edge- and vertex-deletion version. – The weighted version of $\text{textsc}GroupFeedbackVertexSet$ is FPT, even with an oracle access to group operations. – The weighted version of $\text{textsc}DirectedSubsetFeedbackVertexSet$ is FPT. Our study reveals $\text{textsc}DirectedSymmetricMulticut$ as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting.