摘要
重要分离子集是参数化算法在图分离问题中的基石：它们将一个先验的巨大分离子集搜索空间缩减为一个小而结构化的可有效枚举的家族。这一原则在参数化分离问题中取得了显著成功，但并未解决切割-未切割问题，在这些问题中，需要切断某些连接，同时保持给定终端集的连通性。这些连接性保持的要求创造了一种质上不同的结构，传统的重要分离子集方法无法提供正确的可枚举对象。
我们引入了连接性保持的重要分离子集：这些分离子集能够使 $s$ 与 $t$ 断开，同时保持一个指定的终端集与 $s$ 的连通，并且在具有此属性的分离子集中是极端的。我们的主要结果表明，尽管存在额外的连接性约束，最多为 $k$ 的此类分离子集的数量仍然受限于 $2^{O(k^2\log k)}$，并且可以在 $O(2^{O(k^2\log k)} \times n \times T(n,m))$ 的时间内枚举，其中 $T(n,m)$ 是计算最小基数 $s,t$-分离子的时间。这为带有连接约束的重要分离子集方法提供了系统的扩展。关于 $k$ 的二次依赖反映了一个真实现象：在有向图中，我们构造了至少有 $\frac{2^{k^2-1}}{k}$ 个连接性保持的重要分离子集，大小不超过 $k$。
作为应用，我们获得了一个 FPT 算法，用于优化所有最小 $s,t$-分离子集，其中源组件必须包含一个指定的集合 $A$，并避免一个指定的集合 $B$，这一约束模式无法作为标准的切割-未切割实例表示。我们还将该框架应用于节点多方式切割-未切割问题。
博主点评： 这项研究在处理图论中的复杂问题上拓展了重要分离子集的思路，尤其是在保持连通性的情况下。通过引入新的连接性保持分离子集概念，研究者们不仅为图分离问题提供了新的视角，也为实际应用中的优化问题奠定了基础。尤其是 FPT 算法的提出，可能会在计算复杂性上带来突破。