Counting Minimum Cuts (Algorithm)

there may be distinct cuts which are tied for the fewest number of crossing edges. For a concrete example

you could think about a tree. So, if you just look at a star graph, that is hubs and spokes, it's evident that if you isolate any leaf by itself, then you get a minimum cut with exactly one crossing edge. In fact, if you think about it for a little while, you'll see that in any tree you'll have N-1 different minimum cuts, each with exactly one crossing edge. The question concerns counting the number of minimum cuts. Namely, given that a graph may have more than one minimum cut, what is the largest number of minimum cuts that a graph with N vertices can have? We know the answer is at least N-1. We already discussed how trees have N-1 distinct minimum cuts. We know the answer at most something like 2^N, because a graph only has roughly 2^N cuts. In fact, the answer is both very nice and wedged in between. So the answer is exactly N choose 2, where N is the number of vertices. This is also known as N(N-1)/2. So it can be bigger than it is in trees, but not a lot bigger. In particular, graphs have only; undirected graphs have only polynomially many minimum cuts. And that's been a useful fact in a number of different applications. So, I'm going to prove this back to you. All I need is one short slide on the lower bound and then one slide for the upper bound, which follows from properties of the random contraction algorithm.

So for the lower  bound, we don't have to look much beyond our trees example. We're just gonna look at cycles. So for any value of N, consider the N cycle. So here, for example, is the N cycle with N = 8. That would be an octagon. And the key observation is that, just like in the tree, how moving each of the N-1 edges breaks the tree into two pieces and defines the cut. With a cycle, if you remove just one edge, you don't get a cut. The thing remains connected, but if you remove any pair of edges, then that induces a cut of the graph, corresponding to the two pieces that will remain. No matter which pair of edges you remove, you get a distinct pair of groups, distinct cuts. So ranging overall N choose 2 choices of pairs of edges, you generate N choose 2 different cuts. Each of these cuts has exactly two crossing edges, and it's easy to see that's the fewestnpossible. So that's the lower bound, which was simple enough. Let's now move on to the upper bound, which, a purely count-all fact will follow from an algorithm.

So consider any graph that has N vertices, and let's think about the different minimum cuts of that graph. What we're going to use is that the analysis of the contraction algorithm proceeded in a fairly curious way. So remember how we define the success probability of a contraction algorithm. We fixed up front, some min cut (A, B). And we defined the contraction algorithm, the basic contraction algorithm, before the repeated trials. We defined the contraction algorithm as successful, if and only if it output the minimum cut (A, B) that we designated upfront. If it output some other minimum cut, we didn't count it. We said nope, that's a failure. So we actually analyzed a stronger property than what we were trying to solve, which is outputting a given min cut (A, B) rather than just any/all min cut. So how is that useful? Well, let's apply it here. For each of these T minimum cuts of this graph, we can think about the probability that the contraction algorithm outputs that particular min cut. So we're gonna instantiate the analysis with a particular minimum cut (Ai, Bi). And what we proved in the analysis is that the probability that the algorithm outputs the cut (Ai, Bi), not just any all min cut. But, in fact, this exact cut (Ai, Bi) is bounded below by. We, in the end, we made a sloppy inequality. We said it's at least 1/(N^2). But if you go back to the analysis, you'll see that it was, in fact, 2/N(N-1), also known as 1/(N choose 2). So instantiating the contraction algorithm success probability analysis without all of the repeated trials business, we show that for each of these T cuts, for each fixed cut (Ai, Bi), the probability that this algorithm output that particular cut is at least 1/(N choose 2). Let's introduce a name for this event, the event that the contraction algorithm outputs the Ith min cut. Let's call this Si. The key observation is that the Sis are disjoint events. Remember an event is just a subset of stuff that could happen. So one thing that could happen is that the algorithm outputs the Ith main cuts, and by this joint, we just mean that there is no outcome that in a given pair of events. And that's because the contraction algorithm at N to the [inaudible], once it makes its conflicts, it outputs a single cut is a distinct cut. It can only output a dest one of them. Why is it important that these Sis are disjoint events? Well, with disjoint events, the probabilities  add  the probability of the union of a bunch of disjoint events is the sum of the probabilities of constituent events. If you want to think about this pictorially, and just draw a big box, denoting everything that could happen omega, and then these SIs just these  [inaudible] that don't overlap. So S1, S2, S3, and so on. Now the sum or probabilities of this joint events can sum to, at most, 1, right? The probability of all of omega is 1, and these SIs have not overlap and are packed into omega, so the sum of their probabilities is gonna be smaller. We're adding up formally. We have that the sum of the probabilities. Which we can lower bound by the number of different events. And remember there are T different min cuts for some parameter T. For each min cut (Ai, Bi), a lower bound of the probability that, that could spit out as output is 1/(N choose 2). So a lower bound on the sum of all of these probabilities is the number of them, T times the probability lower bound, 1/(N choose 2), and this has got to be at most 1. Rearranging, what do we find? T, the number of different mid-cuts, is bounded above by N choose 2. Exactly the lower bound provided by the N cycle. The N cycle has N choose 2 distinct minimum cuts. No other graph has more. Every graph has only a polynomial number indeed, at most a quadratic number of minimum cuts.