View PDF HTML (experimental)

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.

Submission history

From: Batya Kenig [view email]
[v1] Wed, 19 Nov 2025 20:13:23 UTC (109 KB)
[v2] Thu, 26 Feb 2026 12:57:34 UTC (64 KB)
[v3] Sun, 26 Apr 2026 14:52:27 UTC (60 KB)
[v4] Wed, 1 Jul 2026 12:26:40 UTC (86 KB)