cispa_all_3840.pdf (848.84 kB)

# Parameterized Complexity of Weighted Multicut in Trees

conference contribution

posted on 2023-11-29, 18:23 authored by Esther Galby, Dániel MarxDániel Marx, Philipp SchepperPhilipp Schepper, Roohani Sharma, Prafullkumar TaleThe \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", }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC