Randomized Minimum CutSetting Up the ProblemBlindly GuessingBlindly Guessing Over and OverNot-So-Blindly GuessingAlgorithms Lecture 12: Randomized Minimum CutJaques: But, for the seventh cause; how did you find the quarrel on the seventh cause?Touchstone: Upon a lie seven times removed:–bear your bo dy more seeming, Audrey:–asthus, sir. I did dislike the cut of a certain courtier’s beard: he sent me word, if Isaid his beard was not cut well, he was in the mind it was: this is called the RetortCourteous. If I sent him word again ‘it was not well cut,’ he would send me word, hecut it to please himself: this is called the Quip Modest. If again ‘it was not well cut,’he disabled my judgment: this is called the Reply Churlish. If again ‘it was not wellcut,’ he would answer, I spake not true: this is called the Reproof Valiant. If again ‘itwas not well cut,’ he would say I lied: this is called the Counter-cheque Quarrelsome:and so to the Lie Circumstantial and the Lie Direct.Jaques: And how oft did you say his beard was not well cut?Touchstone: I durst go no further than the Lie Circumstantial, nor he durst not give methe Lie Direct; and so we measured swords and parted.— William Shakespeare, As You Like It Act V, Scene 4 (1600)12 Randomized Minimum Cut12.1 Setting Up the ProblemThis lecture considers a problem that arises in robust network design. Suppose we have a con-nected multigraph1G representing a communications network like the UIUC telephone system, theinternet, or Al-Qaeda. In order to disrupt the network, an enemy agent plans to remove some ofthe edges in this multigraph (by cutting wires, placing police at strategic drop-off points, or payingstreet urchins to ‘lose’ messages) to separate it into multiple components. Since his country is cur-rently having an economic crisis, the agent wants to remove as few edges as possible to accomplishthis task.More formally, a cut partitions the nodes of G into two nonempty subsets. The size of the cut isthe number of crossing edges, which have one endpoint in each subset. Finally, a minimum cut in Gis a cut with the smallest number of crossing edges. The same graph may have several minimumcuts.a bcd e fg hA multigraph whose minimum cut has three edges.This problem has a long history. The classical deterministic algorithms for this problem rely onnetwork flow techniques, which are discussed in another lecture. The fastest such algorithms run inO(n3) time and are quite complex and difficult to understand (unless you’re already familiar withnetwork flows). Here I’ll describe a relatively simple randomized algorithm published by DavidKarger2, who was a Ph.D. student at Stanford at the time.Karger’s algorithm uses a primitive operation called collapsing an edge. Suppose u and v arevertices that are connected by an edge in some multigraph G. To collapse the edge {u, v}, we1A multigraph allows multiple edges between the same pair of nodes. Everything in this lecture could be rephrasedin terms of simple graphs where every edge has a non-negative weight, but this would make the algorithms and analysisslightly more complicated.2David R. Karger∗. Random sampling in cut, flow, and network design problems. Proc. 25th STOC, 648–657, 1994.1Algorithms Lecture 12: Randomized Minimum Cutcreate a new node called uv, replace any edge of the form u, w or v, w with a new edge uv , w, andthen delete the original vertices u and v. Equivalently, collapsing the edge shrinks the edge downto nothing, pulling the two endpoints together. The new collapsed graph is denoted G/{u, v}. Wedon’t allow self-loops in our multigraphs; if there are multiple edges between u and v, collapsingany one of them deletes them all.abc deac dbeabecdA graph G and two collapsed graphs G/{b, e} and G/{c, d}.I won’t describe how to actually implement collapsing an edge—it will be a homework exerciselater in the course—but it can be done in O(n) time. Let’s just accept collapsing as a black boxsubroutine for now.The correctness of our algorithms will eventually boil down the following simple observation:For any cut in G/{u, v}, there is cut in G with exactly the same number of crossing edges. Infact, in some sense, the ‘same’ edges form the cut in both graphs. The converse is not necessarilytrue, however. For example, in the picture above, the original graph G has a cut of size 1, but thecollapsed graph G/{c, d} does not.This simple observation has two immediate but important consequences. First, collapsing anedge cannot decrease the minimum cut size. More importantly, collapsing an edge increases theminimum cut size if and only if that edge is part of every minimum cut.12.2 Blindly GuessingLet’s start with an algorithm that tries to guess the minimum cut by randomly collapsing edges untilthe graph has only two vertices left.GUESSMINCUT (G):for i ← n downto 2pick a random edge e in GG ← G/ereturn the only cut in GSince each collapse takes O(n) time, this algorithm runs in O(n2) time. Our earlier observationsimply that as long as we never collapse an edge that lies in every minimum cut, our algorithm willactually guess correctly. But how likely is that?Suppose G has only one minimum cut—if it actually has more than one, just pick your favorite—and this cut has size k. Every vertex of G must lie on at least k edges; otherwise, we could separatethat vertex from the rest of the graph with an even smaller cut. Thus, the number of incidentvertex-edge pairs is at least kn. Since every edge is incident to exactly two vertices, G must have atleast kn/2 edges. That implies that if we pick an edge in G uniformly at random, the probability ofpicking an edge in the minimum cut is at most 2/n. In other words, the probability that we don’tscrew up on the very first step is at least 1 −2/n.2Algorithms Lecture 12: Randomized Minimum CutOnce we’ve collapsed the first random edge, the rest of the algorithm proceeds recursively (withindependent random choices) on the remaining (n−1)-node graph. So the overall probability P (n)that GUESSMINCUT returns the true minimum cut is given by the following recurrence:P (n) ≥n − 2n· P (n − 1).The base case for this recurrence is P (2) = 1. We can immediately expand this recurrence into aproduct, most of whose factors cancel out immediately.P (n) ≥nYi=3i − 2i=nQi=3(i − 2)nQi=3i=n−2Qi=1inQi=3i=2n(n − 1)12.3 Blindly Guessing Over and OverThat’s not very good. Fortunately, there’s a