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)} \times n \times 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.
Blogger's Review: This research expands the concept of important separators in addressing complex problems in graph theory, particularly under connectivity preservation conditions. By introducing the notion of connectivity-preserving separators, the authors provide a new perspective on graph separation issues, laying the groundwork for optimization problems in practical applications. The introduction of an FPT algorithm could potentially lead to breakthroughs in computational complexity.