# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parameterized by the Size of the Cutset: Twin-width Meets Flow-Augmentation

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

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

##### Fulltext (public)

arXiv:2207.07425.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Hatzel, M., Jaffke, L., Lima, P. T., Masařík, T., Pilipczuk, M., Sharma, R., et al. (2022). Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parameterized by the Size of the Cutset: Twin-width Meets Flow-Augmentation. Retrieved from https://arxiv.org/abs/2207.07425.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1DE8-F

##### Abstract

We show fixed-parameter tractability of the Directed Multicut problem with

three terminal pairs (with a randomized algorithm). This problem, given a

directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$,

$(s_2,t_2)$, and $(s_3,t_3)$, and an integer $k$, asks to find a set of at most

$k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths, all

$s_2t_2$-paths, and all $s_3t_3$-paths. The parameterized complexity of this

case has been open since Chitnis, Cygan, Hajiaghayi, and Marx proved

fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012, and

Pilipczuk and Wahlstr\"{o}m proved the W[1]-hardness of the 4-terminal-pairs

case at SODA 2016.

On the technical side, we use two recent developments in parameterized

algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch,

Pilipczuk, Wahlstr\"{o}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

problem can be in turn encoded as an FO model-checking task over a structure

consisting of a few 0-1 matrices. We look at this problem through the lenses of

twin-width, a recently introduced structural parameter [Bonnet, Kim,

Thomass\'{e}, Watrigant, FOCS 2020]: By a recent characterization [Bonnet,

Giocanti, Ossona de Mendes, Simon, Thomass\'{e}, Toru\'{n}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 the matrices in the said encoding has a large grid minor, a vertex

corresponding to the ``middle'' box in the grid minor can be proclaimed

irrelevant -- not contained in the sought solution -- and thus reduced.

three terminal pairs (with a randomized algorithm). This problem, given a

directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$,

$(s_2,t_2)$, and $(s_3,t_3)$, and an integer $k$, asks to find a set of at most

$k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths, all

$s_2t_2$-paths, and all $s_3t_3$-paths. The parameterized complexity of this

case has been open since Chitnis, Cygan, Hajiaghayi, and Marx proved

fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012, and

Pilipczuk and Wahlstr\"{o}m proved the W[1]-hardness of the 4-terminal-pairs

case at SODA 2016.

On the technical side, we use two recent developments in parameterized

algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch,

Pilipczuk, Wahlstr\"{o}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

problem can be in turn encoded as an FO model-checking task over a structure

consisting of a few 0-1 matrices. We look at this problem through the lenses of

twin-width, a recently introduced structural parameter [Bonnet, Kim,

Thomass\'{e}, Watrigant, FOCS 2020]: By a recent characterization [Bonnet,

Giocanti, Ossona de Mendes, Simon, Thomass\'{e}, Toru\'{n}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 the matrices in the said encoding has a large grid minor, a vertex

corresponding to the ``middle'' box in the grid minor can be proclaimed

irrelevant -- not contained in the sought solution -- and thus reduced.