Help Privacy Policy Disclaimer
  Advanced SearchBrowse





On Weighted Graph Separation Problems and Flow-Augmentation


Sharma,  Roohani
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 889KB

Supplementary Material (public)
There is no public supplementary material available

Kim, E. J., Masařík, T., Pilipczuk, M., Sharma, R., & Wahlström, M. (2022). On Weighted Graph Separation Problems and Flow-Augmentation. Retrieved from https://arxiv.org/abs/2208.14841.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1E78-D
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 \textsc{Directed Feedback Vertex Set}, 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
\textsc{Multicut} is FPT, both in the edge- and vertex-deletion version. -- The
weighted version of \textsc{Group Feedback Vertex Set} is FPT, even with an
oracle access to group operations. -- The weighted version of \textsc{Directed
Subset Feedback Vertex Set} is FPT. Our study reveals \textsc{Directed
Symmetric Multicut} as the next important graph separation problem whose
parameterized complexity remains unknown, even in the unweighted setting.