The Parameterized Complexity Landscape of Two-Sets Cut-Uncut

Matthias Bentert, Fedor V. Fomin, Fanny Hauser +1

In Two-Sets Cut-Uncut, we are given an undirected graph $G=(V,E)$ and two terminal sets $S$ and $T$. The task is to find a minimum cut $C$ in $G$ (if there is any) separating $S$ f…