Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

Meike Hatzel; Lars Jaffke; Paloma Thomé de Lima; Tomáš Masařík; Marcin Pilipczuk; Roohani Sharma; Manuel Sorge

doi:10.1137/1.9781611977554.ch123

Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

Meike Hatzel
, Lars Jaffke
, Paloma Thomé de Lima
, Tomáš Masařík
, Marcin Pilipczuk
, Roohani Sharma
, Manuel Sorge

Algorithms

Max Planck Institute for Informatics
University of Bergen
NII - National Institute of Informatics
University of Warsaw
Vienna University of Technology

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Original language	English
Title of host publication	Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
Publisher	Society for Industrial and Applied Mathematics
Publication date	2023
Pages	3229 - 3244
DOIs	https://doi.org/10.1137/1.9781611977554.ch123
Publication status	Published - 2023
Event	Symposium on Discrete Algorithms - Grand Hotel Mediterraneo, Firenze, Italy Duration: 22 Jan 2023 → 25 Jan 2023 Conference number: 34 https://www.siam.org/conferences-events/past-event-archive/soda23/?utm

Symposium

Symposium	Symposium on Discrete Algorithms
Number	34
Location	Grand Hotel Mediterraneo
Country/Territory	Italy
City	Firenze
Period	22/01/2023 → 25/01/2023
Internet address	https://www.siam.org/conferences-events/past-event-archive/soda23/?utm

Access to Document

10.1137/1.9781611977554.ch123

https://epubs.siam.org/doi/reader/10.1137/1.9781611977554.ch123

Cite this

Hatzel, M., Jaffke, L., Thomé de Lima, P., Masařík, T., Pilipczuk, M., Sharma, R., & Sorge, M. (2023). Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023) (pp. 3229 - 3244). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977554.ch123

@inproceedings{14c9e44edd7c47d98d4e58e4995cf658,

title = "Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation",

author = "Meike Hatzel and Lars Jaffke and \{Thom{\'e} de Lima\}, Paloma and Tom{\'a}{\v s} Masa{\v r}{\'i}k and Marcin Pilipczuk and Roohani Sharma and Manuel Sorge",

year = "2023",

doi = "10.1137/1.9781611977554.ch123",

language = "English",

pages = "3229 -- 3244",

booktitle = "Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)",

publisher = "Society for Industrial and Applied Mathematics",

address = "United States",

note = "Symposium on Discrete Algorithms, SODA ; Conference date: 22-01-2023 Through 25-01-2023",

url = "https://www.siam.org/conferences-events/past-event-archive/soda23/?utm",

}

Hatzel, M, Jaffke, L, Thomé de Lima, P, Masařík, T, Pilipczuk, M, Sharma, R & Sorge, M 2023, Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. in Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics, pp. 3229 - 3244, Symposium on Discrete Algorithms, Firenze, Italy, 22/01/2023. https://doi.org/10.1137/1.9781611977554.ch123

Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. / Hatzel, Meike; Jaffke, Lars; Thomé de Lima, Paloma et al.
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics, 2023. p. 3229 - 3244.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

TY - GEN

T1 - Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation

AU - Hatzel, Meike

AU - Jaffke, Lars

AU - Thomé de Lima, Paloma

AU - Masařík, Tomáš

AU - Pilipczuk, Marcin

AU - Sharma, Roohani

AU - Sorge, Manuel

N1 - Conference code: 34

PY - 2023

Y1 - 2023

U2 - 10.1137/1.9781611977554.ch123

DO - 10.1137/1.9781611977554.ch123

M3 - Article in proceedings

SP - 3229

EP - 3244

BT - Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)

PB - Society for Industrial and Applied Mathematics

T2 - Symposium on Discrete Algorithms

Y2 - 22 January 2023 through 25 January 2023

ER -

Hatzel M, Jaffke L, Thomé de Lima P, Masařík T, Pilipczuk M, Sharma R et al. Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023). Society for Industrial and Applied Mathematics. 2023. p. 3229 - 3244 doi: 10.1137/1.9781611977554.ch123