Using a min-cut generalisation to go beyond Boolean surjective VCSPs

Gregor Matl, Stanislav Zivny

In this work, we first study a natural generalisation of the Min-Cut problem, where a graph is augmented by a superadditive set function defined on its vertex subsets. The goal is…