0:00

So this is short optional video, really just for fun, I want to point

Â out an interesting consequence tracking algorithm has about a

Â problem that is in pure graph theory. So, to motivate the question, I want to remind

Â you of something we discussed in passing, which is that a graph may have more than

Â one minimum cut. So, 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 fewest

Â possible. >>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 outputs 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 <i>add</i> 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.

Â