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
Approach I: Do Karger n^c times (still polynomial, raises exponent on n of c) and compare resulting min cuts. with c >=1
Approach II: When Karger is taken its edges for Contraction, raise probabilty of High weights. Doesnt affect Runtime
or even a combination of both?
Approach I doesn't seem to add anything to Karger's algorithm. From the introduction to this article: "By iterating this basic algorithm a sufficient number of times, a minimum cut can be found with high probability." In other words, Approach I is already part of the algorithm.
Approach II is technically unnecessary (Karger's algorithm will eventually find the minimum cut anyways), and may actively impair the algorithm. For example, consider a graph that can be cut by removing one particular edge, but otherwise requires two or more edges for a cut (the numbers represent the cost of an edge):
If that particular edge has the highest cost (999 in this example), then raising the probability of selecting that edge for contraction reduces the probability of finding the (minimum cost) minimum cut. In fact, it reduces the probability of finding the (any cost) minimum cut.
So all you need to do is run the standard algorithm. On each iteration you need to check if the newly found cut has fewer edges than the current best cut. If so, the newly found cut is the best cut (so far). If the newly found cut has the same number of edges as the current best cut, then compare the costs to see which is better.