查找无法避免在从源到水槽的路径上避免的小节点集

Question

在带有启动节点和结尾节点的有向图中，如何找到一个小（例如最小。 SET S的至少一个成员。该图可能具有循环。这可能很难。是否有近似方法可以从图形中找到一个或几个这样的S？列举和测试每个候选人似乎都不起作用。谢谢。

Answer 1

找到最小数量的 边缘 而不是顶点是著名的最小切割问题，可以使用任何一个可以解决 max-flow-min切割 算法。选择顶点是 广义最大流式定理 可以使用类似的算法来解决它。无论如何，它可以作为一个 多项式复杂性的线性程序, ，可以使用任何LP-Solvers在多项式时间内解决。