<div class="csl-bib-body">
<div class="csl-entry">Hatzel, M., Jaffke, L., LIMA BARBOSA, C. 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 <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA23)</i> (pp. 3229–3244). https://doi.org/10.1137/1.9781611977554.ch123</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/191159
-
dc.description.abstract
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). In this problem we are given a directed graph G, three pairs of vertices (calledterminals) (s1, t1), (s2, t2), (s3, t3), and an integer k and we want to find a set of at most k non-terminalvertices in G that intersect all s1t1-paths, all s2t2-paths, and all s3t3-paths. The parameterized complexity of this problem has been open since Chitnis, Hajiaghayi, and Marx proved fixed-parameter tractability ofthe two-terminal-pairs case at SODA 2012, and Pilipczuk and Wahlström proved the W[1]-hardness of thefour-terminal-pairs case at SODA 2016.
On the technical side, we use two recent developments in parameterized algorithms. Using the techniqueof directed flow-augmentation [Kim, Kratsch, Pilipczuk, Wahlström, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain. We observe that this problemcan be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. Welook at this problem through the lenses of twin-width, a recently introduced structural parameter [Bonnet, Kim, Thomassé, Watrigant, FOCS 2020]: By a recent characterization [Bonnet, Giocanti, Ossona de Mendez,Simon, Thomassé, Toruńczyk, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof, we show an irrelevant vertex rule: If any of thematrices in the said encoding has a large grid minor, a vertex corresponding to the “middle” box in the gridminor can be proclaimed irrelevant — not contained in the sought solution — and thus reduced.
en
dc.language.iso
en
-
dc.subject
DIRECTED MULTICUT problem
en
dc.subject
Parameterized complexity
en
dc.subject
directed flow-augmentation
en
dc.title
Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
University of Copenhagen, Denmark
-
dc.contributor.affiliation
Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
-
dc.relation.isbn
978-1-61197-755-4
-
dc.description.startpage
3229
-
dc.description.endpage
3244
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA23)
-
tuw.peerreviewed
true
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.1137/1.9781611977554.ch123
-
dc.description.numberOfPages
16
-
tuw.author.orcid
0000-0003-3249-1169
-
tuw.author.orcid
0000-0003-4856-5863
-
tuw.author.orcid
0000-0002-0912-8313
-
tuw.author.orcid
0000-0002-8111-344X
-
tuw.event.name
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
en
tuw.event.startdate
22-01-2023
-
tuw.event.enddate
25-01-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.country
IT
-
tuw.event.presenter
Hatzel, Meike
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.grantfulltext
restricted
-
item.openairetype
conference paper
-
item.fulltext
no Fulltext
-
item.languageiso639-1
en
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.cerifentitytype
Publications
-
crisitem.author.dept
Technische Universiät Berlin, Germany
-
crisitem.author.dept
University of Bergen
-
crisitem.author.dept
University of Copenhagen, Denmark
-
crisitem.author.dept
University of Warsaw
-
crisitem.author.dept
University of Warsaw
-
crisitem.author.dept
Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity