On Weighted Graph Separation Problems and Flow-Augmentation

Kim, Eun Jung; Masařík, Tomáš; Pilipczuk, Marcin; Sharma, Roohani; Wahlström, Magnus

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

成果報告書

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

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

arXiv:2208.14841.pdf
(プレプリント), 889KB

付随資料 (公開)

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.

引用: 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.