Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems

Abstract

Important separators are a cornerstone of parameterized algorithms for graph separation: they reduce an a priori enormous search space of separators to a small, structured family that can be enumerated efficiently. This principle has been remarkably successful for parameterized separation problems, but it does not address cut-uncut problems, where one must cut some connections while preserving the connectivity of a given set of terminals. These connectivity-preservation requirements create a qualitatively different type of structure, and the classical important-separator machinery no longer gives the right objects to enumerate. We introduce connectivity-preserving important separators: separators that disconnect $s$ from $t$, keep a prescribed terminal set connected to $s$, and are extremal among separators with this property. Our main result shows that, despite the additional connectivity constraints, the number of such separators of size at most $k$ is bounded by $2^{O(k^2\log k)}$, and they can be enumerated in $O(2^{O(k^2\log k)}\cdot n\cdot T(n,m))$ time, where $T(n,m)$ is the time for computing a minimum-cardinality $s,t$-separator. This gives a systematic extension of the important-separator method with connectivity constraints. The quadratic dependence on $k$ reflects a real phenomenon: in directed graphs, we construct instances with at least $\frac{2^{k^2-1}}{k}$ connectivity-preserving important separators of size at most $k$. As applications, we obtain an FPT algorithm for optimizing over all minimal $s,t$-separators whose source component must contain a prescribed set $A$ and avoid a prescribed set $B$, a constraint pattern not expressible as a standard cut-uncut instance. We also apply the framework to Node Multiway Cut-Uncut.