@online{Kim2208.14841,
TITLE = {On Weighted Graph Separation Problems and Flow-Augmentation},
AUTHOR = {Kim, Eun Jung and Masa{\v r}{\'i}k, Tom{\'a}{\v s} and Pilipczuk, Marcin and Sharma, Roohani and Wahlstr{\"o}m, Magnus},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2208.14841},
EPRINT = {2208.14841},
EPRINTTYPE = {arXiv},
YEAR = {2022},
ABSTRACT = {One of the first application of the recently introduced technique of<br>\emph{flow-augmentation} [Kim et al., STOC 2022] is a fixed-parameter algorithm<br>for the weighted version of \textsc{Directed Feedback Vertex Set}, a landmark<br>problem in parameterized complexity. In this note we explore applicability of<br>flow-augmentation to other weighted graph separation problems parameterized by<br>the size of the cutset. We show the following. -- In weighted undirected graphs<br>\textsc{Multicut} is FPT, both in the edge- and vertex-deletion version. -- The<br>weighted version of \textsc{Group Feedback Vertex Set} is FPT, even with an<br>oracle access to group operations. -- The weighted version of \textsc{Directed<br>Subset Feedback Vertex Set} is FPT. Our study reveals \textsc{Directed<br>Symmetric Multicut} as the next important graph separation problem whose<br>parameterized complexity remains unknown, even in the unweighted setting.<br>},
}