On weighted graph separation problems and flow-augmentation
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913190415171584 |
|---|---|
| author | Kim, Eun Jung Masařík, Tomáš Pilipczuk, Marcin Sharma, Roohani Wahlström, Magnus |
| author_facet | Kim, Eun Jung Masařík, Tomáš Pilipczuk, Marcin Sharma, Roohani Wahlström, Magnus |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_14841 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On weighted graph separation problems and flow-augmentation Kim, Eun Jung Masařík, Tomáš Pilipczuk, Marcin Sharma, Roohani Wahlström, Magnus Data Structures and Algorithms Computational Complexity 68Q27, 68Q25 F.2 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. |
| title | On weighted graph separation problems and flow-augmentation |
| topic | Data Structures and Algorithms Computational Complexity 68Q27, 68Q25 F.2 |
| url | https://arxiv.org/abs/2208.14841 |