algorithm - 保证边不是最小生成树的一部分

我正在解决 Kleinberg 和 Tardos 的 Algorithm Design 书中的练习，遇到了这个不太容易(对我来说)的问题，即找到一条边永远不会属于图的 MST 的保证。问题是这样的:

给定一个图 G = (V, E)，每条边 e 上的成本为 c_e。给定误差参数 epsilon 和 k(均 > 0)，您想确定以下属性 (*) 在多项式时间内是否适用于特定边 e' = (u, v)。

(*) 即使每条边的成本最多改变 epsilon(增加或减少)，并且除了 e' 之外的 k 个边的成本进一步更改为一些任意不同的值，边 e' 仍然会不属于 G 的任何 MST。

我知道 MST 的 cut 属性，但看不到如何将其应用于此问题。提前感谢您的想法!

最佳答案

由于 j_random_hacker 的评论，最终得到了答案。

答案基本上使用 MST 的循环属性 - 如果边是 G 中循环中最昂贵的边，则它不能属于 G 的任何 MST。

将 k 条边的成本更改为任意值的规定意味着我们必须证明 e' 是至少 k+1 个循环中最昂贵的边，除了 e' 本身之外，所有边都不相交。这样，即使 k 个边的任意变化导致 e' 在 k 个循环中不是最昂贵的，它仍然是最后一个循环中最昂贵的。

给定图 G、边 e' 和参数 k 和 epsilon(均 > 0):

临时删除 G 中比 e' 开销更大的所有边(这确保 e' 在我们找到的任何循环中都是开销最大的)

现在，将 e' 的一端设置为源 (s)，将另一端设置为汇 (t)。将所有边的容量设置为 1。流完整性确保由于所有容量都是整数，我们将得到一个完整的流。

看看你是否得到了至少 k+1 的值(value)流。如果是，流分解将为您提供与流的值一样多的从 s 到 t 的边不相交路径。通过向它们添加 e' 将所有这些路径转换为循环 - 这样您就有 k+1(或更多)个循环，其中 e' 是最昂贵的边，并且除了 e' 之外，所有边都不相交。您现在可以安全地说属性 (*) 对 e' 成立。

如果 epsilon 是整数，我有办法处理它。在步骤 1 中，删除所有比 cost(e) + 2*epsilon 更昂贵的边。

关于algorithm - 保证边不是最小生成树的一部分，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19547515/