CISPA
Browse
- No file added yet -

Parameterized Complexity of Weighted Multicut in Trees

Download (848.84 kB)
conference contribution
posted on 2023-11-29, 18:23 authored by Esther Galby, Dániel MarxDániel Marx, Philipp SchepperPhilipp Schepper, Roohani Sharma, Prafullkumar Tale
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", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC