AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

The Edge Multicut problem is a classical cut problem where given an undirected graph G, a set of pairs of vertices 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)∈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 𝚠𝚝:E(G)→ℕ 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.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only

The talk will take place in a hybrid format. The in-person participants will meet in room 024 in building E1 4 (MPII). The virtual participants can join via the zoom meeting link given earlier. If you wish to attend the talk virtually but do not have the password for the zoom room, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.