English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. View item / 
  2. Item Summary

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

On Weighted Graph Separation Problems and Flow-Augmentation

MPS-Authors
/persons/resource/persons255161

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)

arXiv:2208.14841.pdf
(Preprint), 889KB

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

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
Abstract
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.