关于满足至少2重连通恢复要求的最小s-t割问题的求解咨询

你的问题对应最小2-边冗余s-t割（或称为每条s-t路径至少包含两条割边的最小权重边集），核心需求是找到最小权重边集C，满足：

1. 移除C后s无法到达t；
2. 移除C的任意真子集（即放回任意一条边）后，s仍无法到达t。

复杂度结论 #

当k为固定值（此处k=2）时，该问题属于多项式时间可解问题，并非NP难问题。可以通过构造分层图的方式，将其转化为标准的s-t最小割问题求解。

正确的多项式算法 #

分层图构造方法 #

我们可以通过构造分层图将原问题转化为标准最小割：

1. 对原图G中的每个节点v，创建3个副本节点：v⁰、v¹、v²，分别代表路径到达v时已经经过0条、1条、2条割边的状态。
2. 对每个非s/t的节点v，添加边v⁰→v¹和v¹→v²，权重设为一个足够大的数（例如原图所有边权重之和+1，确保这些边不会被选入割集）。
3. 对源节点s，添加边s⁰→s¹和s¹→s²，权重同样设为足够大的数，将s⁰作为分层图的源节点。
4. 对终端节点t，添加边t⁰→t¹和t¹→t²，权重设为足够大的数，将t²作为分层图的终端节点。
5. 对原图中的每条边u→v（权重w），在分层图中添加两条边：u⁰→v¹（权重w）、u¹→v²（权重w）。

构造完成后，求解分层图中s⁰到t²的最小割，该割的权重即为原问题的最优解。

算法原理 #

分层图的状态设计强制要求每条从s⁰到t²的路径必须经过至少两条对应原图割边的边（从u⁰→v¹走第一条割边，再从u¹→v²走第二条割边）。因此，分层图的最小割对应原图中所有s-t路径都被至少两条边覆盖的最小权重边集，恰好满足你的需求。

对贪心方案的说明 #

你当前采用的三次最小割贪心方案存在两个明显问题：

1. 无法保证满足条件（2）：构造出的C+Cs或C+Ct可能存在单条边放回后恢复连通的情况（例如放回C中的某条边后，路径可以绕过Cs/Ct的割边）。
2. 无法保证全局最优：存在最优解并非两层割结构的情况，贪心方案会错过这类更优的解。

内容的提问来源于stack exchange，提问作者Ma Ziyue