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)}.
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.