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 from T under the following “uncut” condition. In the graph ( V, E ∖ C ), the terminals in each terminal set remain in the same connected component. In spite of the superficial similarity to the classic problem Minimum s-t-Cut , Two-Sets Cut-Uncut is computationally challenging. In particular, even deciding whether such a cut of any size exists, is already NP-complete. We initiate a systematic study of Two-Sets Cut-Uncut within the context of parameterized complexity. By leveraging known relations between many well-studied graph parameters, we characterize the structural properties of input graphs that allow for polynomial kernels, fixed-parameter tractability (FPT), and slicewise polynomial algorithms (XP). Our main contribution is the near-complete establishment of the complexity of these algorithmic properties within the described hierarchy of graph parameters. On a technical level, our main results are fixed-parameter tractability for the (vertex-deletion) distance to cographs and an OR-cross composition excluding polynomial kernels for the vertex cover number of the input graph (under the standard complexity assumption NP ¬ ⊆ coNP/poly).