G²OAT seminar: Flow Augmentation - Solving edge cutting problems using a cutting-edge method

When

9. 12. 2024
13:00 – 14:00

Where

Room TH:A-1247

Thákurova 7, Prague 6

Record

Zoom

In the regular Monday seminar of the G²OAT group, Václav Blažej (University of Warwick) will introduce a method that simplifies a minimal cut into a minimum cut, enabling solutions to generalized problems like l -Bundled Cut and l -Skew Multicut. It emphasizes parameterized complexity to tackle these NP-hard problems efficiently, achieving solutions in f(l) \cdot n^{O(1)}.

Event website

Abstract

A recently developed method of reducing a minimal cut into a minimum cut solved a challenging generalization of the classical minimum cut problem. We show how to use this method in detail, along with a few solutions to (restricted version of) l-Bundled cut, l-chain SAT, and l-skew multicut. As many of the considered problems are NP-hard in general, we focus on parameterized complexity - solving them in f(l) ⋅ nᴼ⁽¹⁾ for some computable function f.

The person responsible for the content of this page: Bc. Veronika Dvořáková