tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two corresponding supernodes are contracted. What's wrong?

Karger's algorithm for finding the global min-cut in a graph G(V, E), works by recursively choosing an edge randomly and contracting its two endpoints.
The analysis, starts assuming there is a min-cut of size K; thus the minimum degree of nodes is K -- and this goes for all subsequent recursions, where there can be multiple edges between the nodes, and nodes are actually supernodes containing those nodes which have been grouped together thus far.
The analysis continues by upperbounding the probability of an edge from the min-cut being chosen at each iteration j, by $\frac{k}{0.5k(n-j)}$, where $0.5k(n-j)$, is the minimum number of edges in the (multi-)graph at iteration j.
Now here's the problem, choosing an edge in the multi-graph past the first iteration and contracting its two endpoints, means contracting all the edges between those two endpoints, hence we cannot upperbound the probability of "it" being in the min-cut by the aforementioned value.
I realize that this is conditioned on the event that no edges in the min-cut have been contracted upto this point, however, the point is, that the suggested probability for "the" edge being in the min-cut does not apply anymore, i.e it also has to be conditioned on the fact that the no edge in the min-cut has been cut yet, and more importantly, that its endpoints are in the same partitions in the min-cut, as the other nodes in their corresponding supernodes. This value can be very roughly upperbounded considering that all the edges between the supernodes are not in the min-cut.
I believe that the fault, or rather that there is a fault, can also be readily discerned when considering the expression $\frac{k}{0.5k(n-j)}$ -- the multiplicity of edges is considered when counting the lower bound for edges (the denominator), but then it is completely ignored, when all those edges are contracted, by only considering a single one.

Please enlighten me as to what/if it/there is I am missing.

  • 1
    $\begingroup$ Karger’s algorithm is a very standard algorithm that has been scrutinized in countless lecture notes. Given its simplicity, I doubt there are any faults in it. I suggest finding lecture notes containing a detailed proof. $\endgroup$ – Yuval Filmus May 31 '19 at 6:34
  • $\begingroup$ Karger's algorithm maintains parallel edges, which can appear due to contraction. See for example Figure 4.1 in Arora's notes. $\endgroup$ – Yuval Filmus May 31 '19 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.