Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
This work provides a new algorithmic framework for parameterized cut problems that require both separation and connectivity preservation, addressing a fundamental limitation of existing separator methods.
The paper introduces connectivity-preserving important separators, a new framework for cut problems with connectivity constraints. It shows that the number of such separators of size at most k is 2^{O(k log k)} and can be enumerated efficiently, leading to improved fixed-parameter algorithms for Node Multiway Cut-Uncut with a 2^{O(k log k)} running time for constant equivalence classes, improving on the previous 2^{O(k^2 log k)} dependence.
Graph separation is a central tool in parameterized algorithm design, and important separators are among its most successful ingredients. They yield small, structured families of separators that can be enumerated efficiently, and underlie fixed-parameter algorithms for many problems. However, this framework fundamentally breaks down in cut-uncut settings, where one must separate terminal sets while preserving connectivity inside specified groups of terminals. In such problems, the classical reachability-based notion of importance no longer captures the separators that matter. We introduce connectivity-preserving important separators, a new framework for cut problems with connectivity constraints. Our main result shows that this family is highly structured: the number of connectivity-preserving important separators of size at most $k$ is $2^{O(k \log k)}$, and they can be enumerated within the same bound up to polynomial factors. As an application, we obtain improved fixed-parameter algorithms for Node Multiway Cut-Uncut. In particular, when the number of equivalence classes is constant - including 2-Sets Cut-Uncut - our approach yields a $2^{O(k \log k)}$ running time, improving on the previous $2^{O(k^2 \log k)}$ dependence. More broadly, our results show that separator-based methods can be extended from pure disconnection problems to problems that simultaneously require separation and preservation of connectivity.