The \textsc{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$. \textsc{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 \textsc{Weighted Edge Multicut} one is additionally given a weight function $\texttt{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 \textsc{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 \textsc{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.
History
Preferred Citation
Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma and Prafullkumar Tale. Parameterized Complexity of Weighted Multicut in Trees. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 2022.
Primary Research Area
Algorithmic Foundations and Cryptography
Name of Conference
International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
Legacy Posted Date
2022-10-13
Open Access Type
Unknown
BibTeX
@inproceedings{cispa_all_3840,
title = "Parameterized Complexity of Weighted Multicut in Trees",
author = "Galby, Esther and Marx, Dániel and Schepper, Philipp and Sharma, Roohani and Tale, Prafullkumar",
booktitle="{International Workshop on Graph-Theoretic Concepts in Computer Science (WG)}",
year="2022",
}