algorithm - 带权重的 Karger 算法

Question

Assume that we are given an undirected, unweighted graph G= (V, E) and some cost function c:E→R>0 assigning a positive cost c(e) to each edge e∈E. The goal is to compute a minimum cut of G of minimum cost (i.e., a minimum cost cut among the cuts consisting of the smallest number of edges). Give an algorithm which with high probability finds such a minimum cost minimum cut in polynomial time. What is the running time of your algorithm? Hint: Karger Algorithm

方法一:执行 Karger n^c 次(仍然是多项式，提高 c 的 n 的指数)并比较结果的最小切割。 c >=1

方法二:当 Karger 处于收缩状态时，提高高权重的概率。不影响运行时间

甚至是两者的结合？

Answer 1

方法 我似乎没有向 Karger 的算法添加任何内容。来自 the introduction to this article : “通过将此基本算法迭代足够次数，可以高概率找到最小切割。” 换句话说，方法 I 已经是算法的一部分。

方法 II 在技术上是不必要的(Karger 算法最终会找到最小切割)，并且可能会主动损害算法。例如，考虑一个图，它可以通过删除一条特定的边来进行切割，但在其他情况下需要两条或更多条边进行切割(数字表示一条边的成本):

如果该特定边的成本最高(在此示例中为 999)，则提高选择该边进行收缩的概率会降低找到(最低成本)最小切割的概率 。事实上，它降低了找到(任何成本)最小切割的可能性。

所以您需要做的就是运行标准算法。在每次迭代中，您需要检查新发现的切割是否比当前最佳切割具有更少的边。如果是这样，新发现的切割是最好的切割(到目前为止)。如果新找到的 cut 与当前最佳 cut 的边数相同，则比较成本以查看哪个更好。