# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Parameterized Complexity of Weighted Multicut in Trees

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

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

##### Fulltext (public)

arXiv:2205.10105.pdf

(Preprint), 849KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Galby, E., Marx, D., Schepper, P., Sharma, R., & Tale, P. (2022). Parameterized Complexity of Weighted Multicut in Trees. Retrieved from https://arxiv.org/abs/2205.10105.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1DC8-3

##### Abstract

The Edge Multicut problem is a classical cut problem where given an

undirected graph $G$, a set of pairs of vertices $\mathcal{P}$, and a budget

$k$, the goal is to determine if there is a set $S$ of at most $k$ edges such

that for each $(s,t) \in \mathcal{P}$, $G-S$ has no path from $s$ to $t$. Edge

Multicut has been relatively recently shown to be fixed-parameter tractable

(FPT), parameterized by $k$, by Marx and Razgon [SICOMP 2014], and

independently by Bousquet et al. [SICOMP 2018]. In the weighted version of the

problem, called Weighted Edge Multicut one is additionally given a weight

function $\mathtt{wt} : E(G) \to \mathbb{N}$ and a weight bound $w$, and the

goal is to determine if there is a solution of size at most $k$ and weight at

most $w$. Both the FPT algorithms for Edge Multicut by Marx et al. and Bousquet

et al. fail to generalize to the weighted setting. In fact, the weighted

problem is non-trivial even on trees and determining whether Weighted Edge

Multicut on trees is FPT was explicitly posed as an open problem by Bousquet et

al. [STACS 2009]. In this article, we answer this question positively by

designing an algorithm which uses a very recent result by Kim et al. [STOC

2022] about directed flow augmentation as subroutine.

We also study a variant of this problem where there is no bound on the size

of the solution, but the parameter is a structural property of the input, for

example, the number of leaves of the tree. We strengthen our results by stating

them for the more general vertex deletion version.

undirected graph $G$, a set of pairs of vertices $\mathcal{P}$, and a budget

$k$, the goal is to determine if there is a set $S$ of at most $k$ edges such

that for each $(s,t) \in \mathcal{P}$, $G-S$ has no path from $s$ to $t$. Edge

Multicut has been relatively recently shown to be fixed-parameter tractable

(FPT), parameterized by $k$, by Marx and Razgon [SICOMP 2014], and

independently by Bousquet et al. [SICOMP 2018]. In the weighted version of the

problem, called Weighted Edge Multicut one is additionally given a weight

function $\mathtt{wt} : E(G) \to \mathbb{N}$ and a weight bound $w$, and the

goal is to determine if there is a solution of size at most $k$ and weight at

most $w$. Both the FPT algorithms for Edge Multicut by Marx et al. and Bousquet

et al. fail to generalize to the weighted setting. In fact, the weighted

problem is non-trivial even on trees and determining whether Weighted Edge

Multicut on trees is FPT was explicitly posed as an open problem by Bousquet et

al. [STACS 2009]. In this article, we answer this question positively by

designing an algorithm which uses a very recent result by Kim et al. [STOC

2022] about directed flow augmentation as subroutine.

We also study a variant of this problem where there is no bound on the size

of the solution, but the parameter is a structural property of the input, for

example, the number of leaves of the tree. We strengthen our results by stating

them for the more general vertex deletion version.