2026-08-06T10:16:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22240 2024-12-05T15:32:41Z ddc:004 open_access

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut Bentert, Matthias Fomin, Fedor V. Hauser, Fanny Saurabh, Saket Fixed-parameter tractability Polynomial Kernels W[1]-hardness XP para-NP-Hardness 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Bentert and Fedor V. Fomin and Fanny Hauser and Saket Saurabh 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.14 urn:nbn:de:0030-drops-222400 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.14 eng https://creativecommons.org/licenses/by/4.0/legalcode