algorithm - Multiway Cut Q-我们如何在多项式时间内显示解决方案？

Question

在多路切割问题中，输入是一个无向图 G= (V, E) 和一组终端节点 s1, s2....sk 在 V 中。

Answer 1

1. 这个问题确实可以通过@Aasmund Eldhuset 提出的最小切割最大流量来解决，S1，S2 之间的最小切割实际上是为了分离 S1 和 S2 而需要删除的最小边集。
   请记住，最小切割问题说：

   给定一个图（加权，但您可以w(e)=1用于未加权版本的所有边），找到组合最小权重的边集 - 使得源 (S1) 和接收器 (S2) 将位于不同的连接组件中。

   请注意，这个问题正是您的问题 - 并且可以通过Edmond Karp等一些算法解决- 它在多项式时间内运行

2. 通过对 (S1,S2) 和 (S2,S3) 重复该过程，您将获得 2 组边 E1（对于 S1,S2）和 E2（对于 S2,S3）。
   现在，请注意最佳解决方案（让它成为 OPT）不小于 E1 和 E2（否则 - 由于 OPT 的“切割”将 S1、S2 和 S2、S3 分开 - 它会作为答案返回，而不是E1 或 E2。
   由此我们可以得出结论|OPT| >= max{|E1|,|E2|}。注意|E1 Union E2| <= |E1| + |E2| <= |OPT| + |OPT| = 2|OPT|- 因此E1 Union E2是问题的 2 近似值。

Answer 2

这听起来像是功课，但我突然想到了一个提示：如果你把你的图变成一个流网络，其中每条边的容量为 1，并使用两个终端节点作为源和汇，你可以使用 Edmonds- Karp 在多项式时间内找到两个终端节点之间的流。当你找到最大流量时，最小切最大流量定理告诉你什么？