In the regular Monday seminar of the G²OAT group, Václav Blažej (University of Warwick) explores a novel approach for transforming minimal cuts into minimum cuts, addressing generalized versions of classical cut problems. It emphasizes parameterized complexity techniques to tackle challenging NP-hard problems like l -Bundled Cut, l -Chain SAT, and l -Skew Multicut efficiently.
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.