Parameterized complexity of weighted multicut in trees

DOI10.1007/978-3-031-15914-5_19MaRDI QIDQ6039425zbMATH OpenFDO

Authors Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale

Publication date 5 May 2023

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.10105

zbMATH Keywords

directed flow augmentationweighted digraph pair cutweighted multicut in trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: The Edge Multicut problem is a classical cut problem where given an undirected graph $G$, a set of pairs of vertices $mathcalP$, 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)inmathcalP$, $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 $mathttwt:E(G)omathbbN$ 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.

Cites work

• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Algorithms for cut problems on trees
• Clustering with local restrictions
• Directed subset feedback vertex set is fixed-parameter tractable
• Exact algorithms and applications for tree-like Weighted Set Cover
• Fixed-parameter tractability and data reduction for multicut in trees
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• scientific article; zbMATH DE number 3876616 (Why is no real title available?)
• Multicut in trees viewed through the eyes of vertex cover
• Multicut Is FPT
• Parameterized algorithms
• Parameterized graph separation problems
• Parameterized tractability of multiway cut with parity constraints
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Representative sets and irrelevant vertices: new tools for kernelization
• The Complexity of Multiterminal Cuts

Cited in

(11)

• FPTAS’s for Some Cut Problems in Weighted Trees
• scientific article; zbMATH DE number 3956440 (Why is no real title available?)
• Optimal cuts and partitions in tree metrics in polynomial time
• scientific article; zbMATH DE number 6850362 (Why is no real title available?)
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• An approximation algorithm for the B-prize-collecting multicut problem in trees
• On Weighted Graph Separation Problems and Flow Augmentation
• Parameterized approximation algorithms for weighted vertex cover
• Parameterized approximation algorithms for weighted vertex cover
• Flow-augmentation. I: Directed graphs
• Flow-augmentation. III: Complexity dichotomy for Boolean CSPS parameterized by the number of unsatisfied constraints

This page was built for publication: Parameterized complexity of weighted multicut in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6039425)