Karger's Algorithm

Hypatia

So...I'm stuck. Can anyone explain Karger's algorithm for finding cuts/min-cuts in non algorithm language, as though to someone who doesn't understand anything but the most basic probability? I'm finding the notation used unreadable and my professor's comments of, "It's self evident" are not helping at all.

Specifically: I understand the principle behind it, you contract edges until you just have 2 nodes left, and the edges in that node are a cut. I'm failing to see how to get a min-cut, how to calculate the probability even with the notes with the equations, and it's supposed to be the key to two of my homework problems and I'm completely stumped.

Hirocon

Are you working with weighted or unweighted graphs?

It's important to understand that the algorithm is not guaranteed to produce a minimal cut; it's just more likely to produce smaller cuts than larger cuts.

In the unweighted case:

You start with a graph. Each step in the algorithm reduces the number of vertices in the graph by 1, producing a smaller graph. At each step, any cut of the smaller graph corresponds to a cut of the original graph.

The minimal cut of an unweighted graph, by definition, is the cut with the lowest number of edges. If you choose an edge at random to remove from a graph, it is relatively unlikely that you will choose an edge that comes from a minimal cut simply because the minimal cut has a small number of edges. If you choose an edge that's not in a minimal cut of the graph and merge the vertices of that edge, then the minimal cut of the new graph will be the same as the minimal cut of the old graph. If this happens to be true at every step of the algorithm, then the minimal cut of the final graph will equal the minimal cut of the original graph.

Take the example below:



The minimum cut of this graph is {{A}, {B, C, D, E, F, G, H, I, J}}. Karger's algorithm will produce this cut as long as the edges {A, B} and {A, C} are never chosen to be merged. At each step, it is very unlikely either of these edges will be chosen to be merged, simply because there are only two of them.

That's the general principle behind the algorithm as I understand it. What sort of probability questions do you need to answer?

Hypatia

Thank you very much for the explanation, that actually helps a lot! All the notation for a lot of the examples given just has me in a confused mess. I think I've bungled my way through the first problem--the specifics of the second which is where I'm stuck on this probability thing is:

Consider the following analogue of Karger's algorithm for finding minimum s-t cuts. We will contract edges iteratively using the following randomized procedure. In a given iteration, let s and t denote the possibly contracted nodes that contain the original nodes s and t, respectively. To make sure htat s and t do not get contracted, at each iteration we delete any edges connecting s and t and select a random edge to contract among the remaining edges. Give an example to show that the probability that this method finds a minimum s-t cut can be exponentially small.